C. Make It Good

C. Make It Good

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array 𝑎$a$ consisting of 𝑛 integers. You have to find the length of the smallest (shortest) prefix of elements you need to erase from 𝑎$a$ to make it a good array. Recall that the prefix of the array 𝑎=[𝑎1,𝑎2,…,𝑎𝑛] is a subarray consisting several first elements: the prefix of the array 𝑎$a$ of length 𝑘$k$ is the array [𝑎1,𝑎2,…,𝑎𝑘](0≤𝑘≤𝑛$0\le k\le n$).

The array 𝑏$b$ of length 𝑚$m$ is called good, if you can obtain a non-decreasing array 𝑐(𝑐1≤𝑐2≤⋯≤𝑐𝑚) from it, repeating the following operation 𝑚 times (initially, 𝑐 is empty):

• select either the first or the last element of 𝑏, remove it from 𝑏, and append it to the end of the array  𝑐. 

For example, if we do 4$4$ operations: take 𝑏1, then  𝑏𝑚, then 𝑏𝑚−1 and at last 𝑏2, then  𝑏 becomes [b3,b4,…,bm−3]and 𝑐=[𝑏1,𝑏𝑚,𝑏𝑚−1,𝑏2].

Consider the following example: b=[1,2,3,4,4,2,1]. This array is good because we can obtain non-decreasing array 𝑐$c$ from it by the following sequence of operations:

1. take the first element of 𝑏, so 𝑏=[2,3,4,4,2,1], 𝑐=[1]; 
2. take the last element of 𝑏, so 𝑏=[2,3,4,4,2], 𝑐=[1,1]; 
3. take the last element of 𝑏, so 𝑏=[2,3,4,4], 𝑐=[1,1,2]; 
4. take the first element of 𝑏, so 𝑏=[3,4,4], 𝑐=[1,1,2,2]; 
5. take the first element of 𝑏, so 𝑏=[4,4], 𝑐=[1,1,2,2,3]; 
6. take the last element of 𝑏, so 𝑏=[4], 𝑐=[1,1,2,2,3,4]; 
7. take the only element of 𝑏, so 𝑏=[], 𝑐=[1,1,2,2,3,4,4] — 𝑐 is non-decreasing. 

Note that the array consisting of one element is good.

Print the length of the shortest prefix of 𝑎 to delete (erase), to make 𝑎 to be a good array. Note that the required length can be 0.

You have to answer 𝑡 independent test cases.

Input

The first line of the input contains one integer 𝑡 (1≤𝑡≤2⋅104) — the number of test cases. Then  𝑡 test cases follow.

The first line of the test case contains one integer 𝑛 (1≤𝑛≤2⋅105) — the length of 𝑎. The second line of the test case contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤2⋅1051≤ai≤2⋅105), where 𝑎𝑖ai is the 𝑖-th element of 𝑎.

It is guaranteed that the sum of 𝑛$n$ does not exceed 2⋅105$2\cdot {10}^5$ (∑𝑛≤2⋅105$\sum n\le 2\cdot {10}^5$).

Output

For each test case, print the answer: the length of the shortest  prefix of elements you need to erase from 𝑎 to make it a good array.

Example

input

Copy

5
4
1 2 3 4
7
4 3 3 8 4 5 2
3
1 1 1
7
1 3 1 4 5 3 2
5
5 4 3 2 3

output

Copy

0
4
0
2
3

Note

In the first test case of the example, the array 𝑎 is already good, so we don't need to erase any prefix.In the second test case of the example, the initial array 𝑎 is not good. Let's erase first 4 elements of 𝑎, the result is [4,5,2]. The resulting array is good. You can prove that if you erase fewer number of first elements, the result will not be good.