B. Restaurant Sorting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

MgRonalds recently received an upgrade with self-order kiosks!

You are given a stack of $$$n$$$ integers, $$$p_{1 \dots n}$$$ where $$$p_1$$$ is the bottom of the stack and $$$p_n$$$ is the top. Determine the minimum $$$k$$$ such that it is possible to pop $$$k$$$ elements off the back of the stack and re-insert them in sort order so that the stack is sorted in ascending order.

Input

The first line of input contains a single integer $$$T$$$, the number of testcases $$$(1 \leq T \leq 6633)$$$. $$$T$$$ testcases follow.

The first line of a testcase contains a single integer $$$n$$$, the number of elements in the stack.

The following line contains $$$n$$$ spaced integers $$$p$$$, the elements in the stack $$$(1 \leq p_i \leq n)$$$. It is guaranteed that all $$$p_i$$$ are distinct.

It is also guaranteed that the sum of $$$n$$$ across all testcases will not exceed $$$2 \cdot 10^5$$$.

 —

Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth an equal amount of points.

For tests $$$1 - 5$$$, the sum of $$$n$$$ across all testcases will not exceed $$$3366$$$.

Output

For each testcase, output one integer $$$k$$$ on a new line denoting the minimum number of elements that need to be popped in order to sort the stack.

Example
Input
5
3
1 2 3
2
2 1
4
4 3 2 1
4
1 4 2 3
7
1 2 3 6 4 7 5
Output
0
2
4
3
4
Note

In the first testcase, the stack is already sorted.

In the second testcase, the entire stack must be popped off to be sorted in the correct order.

In the fourth testcase, it is only necessary to pop off the last $$$3$$$ elements $$$[1, 4, 2, 3] \rightarrow [1] \rightarrow [1, 2, 3, 4]$$$.

 —

Problem Idea: 3366

Problem Preparation: 3366

Occurrences: Novice $$$2$$$