5min 秒了。

xixisuper：多打 ABC 多见原题。

首先是一个常见题意转化，交换相邻元素使序列变有序的最小次数等价于数这个序列的逆序对个数。

但是这题让求变成循环同构序列的的最小交换次数，怎么做呢？

考虑一种映射，假设我们的目标序列是 $a=\{x,x+1,\cdots,n,1,2\cdots x-1\}$，那么我们把 $a_i\to i$ 上，就又变成了求逆序对个数了。

最后考虑如何实现这种映射，不难想到的是先令让值域变成 $0\sim n-1$，然后映射就相当于是把 $a_i\to (a_i+k)\bmod n$ 上。

最后我们对于 $k\in[0,n-1]$ 中的每一个 $k$ 求出对应的操次数，然后输出最小值就是答案。

而转化后的题目实际上就是ABC396F，。

转化后怎么做呢？考虑任意两位之间的贡献：

当 $k$ 属于上述蓝色箭头部分时会产生贡献。

贡献等价于蓝色箭头部分的贡献减去橙色部分箭头的贡献。

用树状数组计算贡献，然后改变差分数组即可，时间复杂度 $O(n\log n)$。

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=4e5+10;
inline ll lowbit(ll x){return x&(-x);}
ll sum[N];
void add(ll x){for(ll i=x;i<N;i+=lowbit(i)) sum[i]+=1;}
ll query(ll x){
	ll ret=0;
	for(ll i=x;i;i-=lowbit(i)){ret+=sum[i];}
	return ret;
}
void init(){for(ll i=0;i<N;i++) sum[i]=0;}
ll n,m,a[N],cha[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;m=n;
	for(ll i=1;i<=n;i++){cin>>a[i];a[i]--;}
	for(ll i=n;i>=1;i--){
		add(a[i]+1);
		ll dt=query(a[i]);
		cha[0]+=dt;
		cha[m-a[i]]-=dt;
		dt=query(m+1)-query(a[i]+1);
		cha[m-a[i]]-=dt;
	}
	init();
	for(ll i=1;i<=n;i++){
		add(a[i]+1);
		ll dt=query(m+1)-query(a[i]+1);
		cha[m-a[i]]+=dt;
		dt=query(a[i]);
		cha[m-a[i]]+=dt;
	}
	ll ans=cha[0];
	for(ll i=1;i<m;i++){
		cha[i]+=cha[i-1];
		ans=min(ans,cha[i]);
	}
	cout<<ans;
	return 0;
}