示例：3 4 1 5 2 所有满足条件的序列： 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 分别求 3 4 1 5 2 经过多少次交换可以变成以上 4 种序列，选其中交换次数最少到。 要求 3 4 1 5 2 经过多少次交换可以变成 2 3 4 5 1，可以将 1 改为 6，然后求逆序对数量。 同理求：3 4 1 5 2 经过多少次交换可以变成 3 4 5 1 2，只需要将 1 改为 6，2改为 7 求逆序对。 考虑以下两个序列中的逆序对数的区别： 3 4 1 5 2 3 4 6 5 2 a. 1 前面的所有数都和 1 形成逆序对。 b. 6 后面的所有数都和 6 形成逆序对。 设值 i 所在位置为 p[i]，则：减少了 p[i]-1 个逆序对，增加了 n-p[i]个逆序对。 设当前序列逆序对数量为 cnt，当前最小值为 i，则将 i 修改为最大值后逆序对数量变为： cnt - (p[i] - 1) + (n - p[i]); 只需要做一次求逆序对即可，总时间复杂度降为 O(Nlog(N) + N)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, a[N], pos[N]; ll c[N];

void add(int x) { for (; x <= n; x += x & -x) ++c[x]; }
ll sum(int x) { ll res = 0; for (; x; x -= x & -x) res += c[x]; return res; }

int main() {
    scanf("%d", &n);
    memset(c, 0, sizeof(c));
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        add(a[i]);
        ans += i - sum(a[i]);
        pos[a[i]] = i;
    }
    ll t = ans;
    for (int i = 1; i <= n; ++i) { // 转移
        t = t - (pos[i] - 1) + (n - pos[i]);
        // 即将把 i 看成 i+n，那么i之前有 pos[i]-1 个 i 大的，i 后面有 n-pos[i]个比 i 小的
        ans = min(ans, t);
    }
    printf("%lld\n", ans);
    return 0;
}

/*
示例：3 4 1 5 2 
所有满足条件的序列：
	2 3 4 5 1
	3 4 5 1 2
	4 5 1 2 3
	5 1 2 3 4
分别求 3 4 1 5 2 经过多少次交换可以变成以上 4 种序列，选其中交换次数最少到。
要求 3 4 1 5 2 经过多少次交换可以变成 2 3 4 5 1，可以将 1 改为 6，然后求逆序对数量。
同理求：3 4 1 5 2 经过多少次交换可以变成 3 4 5 1 2，只需要将 1 改为 6，2改为 7 求逆序对。
考虑以下两个序列中的逆序对数的区别：
	3 4 1 5 2
	3 4 6 5 2
	a. 1 前面的所有数都和 1 形成逆序对。
	b. 6 后面的所有数都和 6 形成逆序对。
设值 i 所在位置为 p[i]，则：减少了 p[i]-1 个逆序对，增加了 n-p[i]个逆序对。
设当前序列逆序对数量为 cnt，当前最小值为 i，则将 i 修改为最大值后逆序对数量变为：
cnt - (p[i] - 1) + (n - p[i]); 
只需要做一次求逆序对即可，总时间复杂度降为 O(Nlog(N) + N)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,a[N],pos[N]; ll c[N];

void add(int x){for(;x<=n;x+=x&-x)++c[x];}
ll sum(int x){ll res=0;for(;x;x-=x&-x)res+=c[x];return res;}
int main()
{
    scanf("%d",&n);
    memset(c,0,sizeof(c));
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        add(a[i]);
        ans+=i-sum(a[i]);
        pos[a[i]]=i;
    }
    ll t=ans;
    for(int i=1;i<=n;++i)//转移
    {
        t=t-(pos[i]-1)+(n-pos[i]);
        //即将把 i 看成 i+n，那么i之前有 pos[i]-1 个 i 大的，i 后面有 n-pos[i]个比 i 小的
        ans=min(ans,t);
    }
    printf("%lld\n",ans);
    return 0;
}