Sequence in the Pocket【思维+规律】

Sequence in the Pocket

DreamGrid has just found an integer sequence 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?

Input

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

The first line contains an integer (), indicating the length of the sequence.

The second line contains integers (), indicating the given sequence.

It's guaranteed that the sum of of all test cases will not exceed .

Output

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

Sample Input

Sample Output

2
0

Hint

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.

题意：

给出T组每组一个序列每次操作可以把其中的一个数移动到最前方需要几次操作可以将序列变成从小到大

思路：

将序列从小到大排序然后将新的序列从后往前每次枚举一个值在原序列中查找出来num个所以需要移动的次数是n-num

例如：

1 2 3 1 2 3 排序后是 1 1 2 2 3 3

依次枚举3 3 2 2 1 1

3 可以找到 j=n-1 时

3可以找到 j=n-4时

2可以找到 j=n-5时

在枚举第二个2的时候就找不到了（j一直在减小）

代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX=1e5;
int main()
{
    int a[MAX+5],b[MAX+5],T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b,b+n);
        int j=n-1,num=0;
        for(int i=n-1;i>=0;i--){  ///for+while 这种写法很好 
            while(b[i]!=a[j]&&j>=0){
                j--;
            }
            if(j<0){
                break;
            }
            else{
                num++;
                j--;
                //printf("%d ",b[i]);
            }
        }
       // printf("
");
        printf("%d
",n-num);
    }
    return 0;
}