木の形の配列は正の序数と逆の序数-hdu Minimum Inversion Numberを求めます

/*

      0 

  1

        

C(n,2)-       

            

      

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)

a1  an-a1  a1  ，（a1-1）  a1  (-1   ),    

ans+=(n-a1)-(a1-1)

*/

#include<stdio.h>

#include<string.h>

#define MAXN 5050

int c[MAXN];

int n;

int lowbit(int x)

{

	return x&(-x);

}

void update(int i,int val)

{

	while(i<=n)

	{

		c[i]+=val;

		i+=lowbit(i);

	}

}

int query(int i)

{	

	int s=0;

	while(i>0)

	{

		s+=c[i];

		i-=lowbit(i);

	}

	return s;

}

int a[MAXN];

int main()

{

	int i;

	while(scanf("%d",&n)!=EOF)

	{

		int ans=0;

		memset(c,0,sizeof(c));

		for(i=1;i<=n;i++)

		{

			scanf("%d",&a[i]);

			a[i]++;

			ans+=query(a[i]);

			update(a[i],1);

		}

		int min=n*(n-1)/2-ans;

		ans=min;//            WA

		for(i=1;i<=n;i++)

		{

			ans+=n-a[i]-(a[i]-1);

			if(ans<min)

				min=ans;

		}

		printf("%d
",min);

	}

	return 0;

}