O($n^2$)优化+逆向思维搜索，竟然AC了

#include<bits/stdc++.h>
#define re register
using namespace std;
int a[100001],b[100001];
int main()
{
	int n;
	scanf("%d",&n);
	for(re int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int ans=0;
	for(re int i=1;i<=n;i++)
	{
		if(b[i]!=a[i])
		{
			for(re int z=n;z>=i+1;z--)
			{
				if(a[z]==b[i])
				{
					swap(a[i],a[z]);
					ans++;
					break;
				}
			}
		}
	}
	printf("%d",ans);
}