Open at Both Ends - Repovive Standard Round 6 | Repovive

18B. Open at Both Ends

1000 pts1s256 MB

There are $n$ books on a shelf, numbered from $1$ to $n$ . From left to right, their current order is the permutation $p_1,p_2,\ldots,p_n$ .

The shelf is sorted if the books appear in the order $1,2,\ldots,n$ .

In one operation, you may choose the leftmost or the rightmost book, remove it from the shelf, and insert it at any position. In particular, you may insert it at either end of the shelf.

Find the minimum number of operations needed to sort the shelf.

Constraints

$1 \le t \le 10^3$
$1 \le n \le 10^5$
The sum of $n$ over all test cases is at most $10^5$
$p$ is a permutation of $1,2,\ldots,n$

Input

The input consists of multiple test cases.

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

Output

For each test case, output the minimum number of operations needed to sort the shelf.

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

4
4 2 3 1

Case 2

5
1 2 3 4 5

Case 3

5
5 4 3 2 1

Explanation

Case 1

One optimal sequence is:

Remove book $1$ from the right end and insert it between books $4$ and $2$ , obtaining $4,1,2,3$ .
Remove book $4$ from the left end and insert it at the right end, obtaining $1,2,3,4$ .

One operation cannot be enough. If book $4$ is moved, the remaining books are in the order $2,3,1$ ; if book $1$ is moved, they are in the order $4,2,3$ . Neither order can be part of the sorted shelf.

Case 2

The shelf is already sorted, so no operation is needed.

Case 3

The books are initially in decreasing order. Any two books that are never moved would stay in decreasing relative order, so at least four books must be moved.

Four operations are sufficient:

5,4,3,2,1 \to 5,4,1,3,2 \to 5,4,1,2,3 \to 4,1,2,3,5 \to 1,2,3,4,5.

Output

Case 1

Case 2

Case 3

Input

Case 1

8
8 1 3 5 6 2 4 7

Case 2

10
2 5 8 9 1 3 4 6 7 10

Explanation

Case 1

The shelf can be sorted in four operations, and three operations are not sufficient.

Case 2

The minimum number of operations is four.

Output

Case 1

Case 2

There are $n$ books on a shelf, numbered from $1$ to $n$ . From left to right, their current order is the permutation $p_1,p_2,\ldots,p_n$ .

The shelf is sorted if the books appear in the order $1,2,\ldots,n$ .

In one operation, you may choose the leftmost or the rightmost book, remove it from the shelf, and insert it at any position. In particular, you may insert it at either end of the shelf.

Find the minimum number of operations needed to sort the shelf.

$1 \le t \le 10^3$
$1 \le n \le 10^5$
The sum of $n$ over all test cases is at most $10^5$
$p$ is a permutation of $1,2,\ldots,n$

The input consists of multiple test cases.

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

For each test case, output the minimum number of operations needed to sort the shelf.

\left. \begin{array}{l} ans \end{array} \right\} \times t

One optimal sequence is:

Remove book $1$ from the right end and insert it between books $4$ and $2$ , obtaining $4,1,2,3$ .
Remove book $4$ from the left end and insert it at the right end, obtaining $1,2,3,4$ .

The books are initially in decreasing order. Any two books that are never moved would stay in decreasing relative order, so at least four books must be moved.

Four operations are sufficient:

5,4,3,2,1 \to 5,4,1,3,2 \to 5,4,1,2,3 \to 4,1,2,3,5 \to 1,2,3,4,5.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

18B. Open at Both Ends

Constraints

Input

Output

Samples

18B. Open at Both Ends

Constraints

Input

Output

Samples