我的想法是预处理一个 $cnt_{i,j}$ 表示占着 $i$ 最终位置的 $j$ 的个数（$1\le i,j\le 4$），然后对这个数组进行计算。

但是我不知道接下来怎么搞，请大佬提供思路，下面是代码半成品：

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, a[N], b[N];
int cnt[6][6]; 

int main(){
	scanf("%d", &n);
	for(int i=1;i<=n;i++){
		scanf("%d", &a[i]);
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
	for(int i=1;i<=n;i++)
		cnt[b[i]][a[i]]++;//cnt[i][j] 表示占着 i 最终位置的 j 的个数
	int ans = 0;
	for(int i=1;i<=3;i++){
		for(int j=i+1;j<=4;j++){
			int d = min(cnt[i][j], cnt[j][i]);
			ans += d;
			cnt[i][j] -= d, cnt[j][i] -= d;
		}
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			if(i == j)
				continue;
			ans += cnt[i][j];
		}
	}
	printf("%d\n", ans - 1);
	return 0;
}