思路
对于每次操作，会把序列分成两个部分，两部分之间不会排序。
考虑仅每次排一个数字，理由如下：
假设已经排好了 \(1,2,3\cdots i-1\) 的顺序，对于数字 \(i\)，如果 \(i+1\) 在该数字的前面，那么 \(k\) 应选择为 \(i+1\)，这样才能排好 \(i\) 和 \(i+1\)。如果选择的 \(k\) 大于 \(k+1\) 那么还是需要再排一次使 \(i\) 和 \(i+1\) 的顺序正确，操作数不变，只是操作顺序不同。
所以我们可以枚举 \(i\)，如果 \(i+1\) 在前面，则需要排序，如果在后面，则不需要排序，记录排序次数就好。
因为需要快速知道两个数的位置关系，可以提前存下来。
AC code
#include <bits/stdc++.h>
using namespace std;
int T,n,a,ans;
map<int,int>m;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n),ans=0;
for(int i=1;i<=n;++i) scanf("%d",&a),m[a]=i;
for(int i=1;i<n;++i) if(m[i+1]<m[i]) ++ans;
printf("%d\n",ans);
}
return 0;
}