以下代码都能通过，最坏时间复杂度为 $O(n^2)$，结果过了。。。

#include <bits/stdc++.h>
#define N 2000005
#define endl '\n'
using namespace std;
int n,a[N],id[N],ans,v[N],jt;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],id[a[i]]=i,jt+=(a[i]==i?1:0);
	if(jt==n)
	{
		cout<<0;
		return 0;
	}
	if(a[n]!=n)
	{
		cout<<-1;
		return 0;
	}
	for(int i=n-1;i>1;i--)
	{
		for(int j=id[i]+1;j<n;j++)
		{
			if(i>a[j])
			{
				ans++,a[id[i]]=1e9;
				break;
			}
		}
	}
	cout<<ans;
	return 0;
}

hack 数据：

输入：

2000000
2 1 3 4 5... 2000000

输出：

1

而上面的代码会超时。