Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4104
Sequence in the Pocket

Time Limit: 2 Seconds      Memory Limit: 65536 KB

DreamGrid has just found an integer sequence $a_1, a_2, \dots, a_n$ in his right pocket. As DreamGrid is bored, he decides to play with the sequence. He can perform the following operation any number of times (including zero time): select an element and move it to the beginning of the sequence.

What's the minimum number of operations needed to make the sequence non-decreasing?


There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), indicating the given sequence.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.


For each test case output one line containing one integer, indicating the answer.

Sample Input

1 3 2 4
2 3 3 5 5

Sample Output



For the first sample test case, move the 3rd element to the front (so the sequence become {2, 1, 3, 4}), then move the 2nd element to the front (so the sequence become {1, 2, 3, 4}). Now the sequence is non-decreasing.

For the second sample test case, as the sequence is already sorted, no operation is needed.

Author: WENG, Caizhi
Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status