> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/hashmap-and-hashset-and-sliding-window/morning-assembly.md).

# Morning Assembly

Eveyone remember standing for queue in school assembly. One day few students were late in the morning assembly, so they just went and stood at the end of the queue. But their Principal was strict and made them stand in ascending order to their height.\
Given an array of N elements representing the shortest person with 1 and tallest with N. He thought to arrange queue by following a trick,Trick was simple: pick a student and send him/her at last or first and to arrange according to height. But he needs your help to do so.\
Cost is increased by one if one student is sent at first or last.

**Input:**\
First line consists of T test cases. First line of test case consists of N. Second line of every test case consists of N elements.

**Output:**\
Single line output, print the minimum cost to do so.

**Constraints:**\
1<=T<=100\
1<=N<=10^5

**Example:**\
**Input:**\
2\
3\
2 1 3\
4\
4 3 1 2\
**Output:**\
1\
2

```java
class Solution {
    // arr[i] -> [1,N]
    // 1,3,2,4,7,5,9,6,8
    // Find the longest consecutive subsequence
    // then answer = length - longest consecutive subsequence
    public static int minCost(int[] arr, int n) {
        // Map of Element -> Longest Consecutive subsequence in array [0,Element's index]
        // (including this element)
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int x : arr) {
            if (map.containsKey(x - 1))
                map.put(x, map.get(x - 1) + 1);
            else
                map.put(x, 1);
            max = math.max(max, map.get(x));
        }
        return n - max;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/hashmap-and-hashset-and-sliding-window/morning-assembly.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.