关于#c++#的问题，如何解决？（书的排列顺序）

Question

题目描述
马克家收藏了一套书，这套书叫《OIER故事集》，这套书有n本，每本书有一个编号，从1号到n号。马克把这些书按照编号从小到大，从上往下摞成一摞。马克对这套书很珍视，不允许其他人动。有一天一格到马克家玩，马克一时没有时间，就让一格自己呆在家里。一格因为对这套书非常好奇，偷偷的看了一下，结果发现书中竟然有ljs和commonc的故事。一格看的入了迷，结果把一摞书的顺序弄乱了。眼看着马克就要回来了，一格需要把书恢复到原状，由于每本书都比较重，所以一格能做的操作是把一本书从书堆中抽出来，然后把这本书放到书堆的顶部。给你打乱的书的顺序，你能帮一格算算最少需要几次上述操作，才能恢复书的顺序。

输入格式
输入包含多组数据。
第一行包含一个正整数T(T<=10)，表示数据组数。
对于每组数据，第一行为一个整数n。
接下来的一行有n个用空格分开的正整数，表示一格打乱后的书的顺序，从上到下。

输出格式
对于每组数据，输出一行一个整数，表示一格最少经过几次操作才能恢复书的顺序。

输入样例
2
4
4 1 2 3
5
1 2 3 4 5

输出样例
3
0

数据范围与提示
【样例说明】
样对于第一组数据，我们先把3号书放在最上面，接着操作2号书，最后操作1号书，4 1 2 3 3 4 1 2 2 3 4 1 1 2 3 4 这样就有序了。
对于第二组数据，已经有序就不需要挪了。
【数据规模与约定】
对于 50% 的数据满足 n<=10。
对于 80%的数据满足 n<=1000。
对于 100% 的数据满足 n<=100000。

Answer 1

#include<iostream>
using namespace std;
const int maxn = 100005;
int a[maxn];
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;;
        for (int i = 1; i <= n; i++)
            cin>>a[i];
        int p = n, cnt = 0;
        for (int i = n; i >= 1; i--)
            if (a[i] == p)p--, cnt++;
        cout << n - cnt << endl;
    }
    return 0;
}