The inversion number of a given number sequence a1, a2, …, an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.

For a given sequence of numbers a1, a2, …, an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:

a1, a2, …, an-1, an (where m = 0 - the initial seqence)
a2, a3, …, an, a1 (where m = 1)
a3, a4, …, an, a1, a2 (where m = 2)
…
an, a1, a2, …, an-1 (where m = n-1)

You are asked to write a program to find the minimum inversion number out of the above sequences.
Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.
Output
For each case, output the minimum inversion number on a single line.
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16

题目意思：大体上说的是求出n次变换中最小的逆序数的个数，不能暴力去模拟，用线段树做，总结出规律，把第一个数放到后面，整个序列改变的逆序数个数=他前面数的个数-第一个数后面的个数。tql %%%大佬们，我蒟蒻。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const	int N=10010;
int w[N];
int a[N];
int b[N];
struct node{
	int l;
	int r;
	int sum;
}tr[N*4];
void pushup(int u)
{
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void build(int u,int l,int r)
{
	tr[u]={l,r,0};
	if(l==r)	return;
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}
void modify(int u,int x,int d)
{
	if(tr[u].l==x&&tr[u].r==x)
	{
		tr[u].sum+=d;
		return ;
	}
	int mid=tr[u].l + tr[u].r>>1;
	if(x<=mid)	modify(u<<1,x,d);
	else		modify(u<<1|1,x,d);
	pushup(u);
}
int query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)
	return tr[u].sum;
	int mid=tr[u].l+tr[u].r>>1;
	ll sum=0;
	if(l<=mid)		sum+=query(u<<1,l,r);
	if(r>mid)		sum+=query(u<<1|1,l,r);
	return sum;	
}
ll res;
int main()
{
	int n;
	while(cin>>n)
{memset(tr,0,sizeof tr);
	build(1,1,n);
	
		for(int i=1;i<=n;i++)
	{
		cin>>w[i];
		w[i]++;
	}
	ll cnt=0;
	ll res=1e9;
	for(int i=1;i<=n;i++)
	{
	modify(1,w[i],1);
	cnt+=query(1,w[i]+1,n);	
	}
	res=min(res,cnt);
	for(int i=1;i<=n;i++)
	{
		if(w[i]-1>=1)cnt-=query(1,1,w[i]-1);
	if(w[i]+1<=n)	cnt+=query(1,w[i]+1,n);
		res=min(res,cnt);
	}
	cout<<res<<endl;
		}
    return 0;
}