#include
#include
int ans,a[5050],b[5050];
void merge(int left,int mid,int right)
{
??? int i,j,cnt=0;
??? int *p;
??? p=(int *)malloc((right-left+1)*sizeof(int));
??? i=left;
??? j=mid+1;
??? while(i<=mid&&j<=right)//这时候i 和 j 指向的部分都排序完毕了 现在合并
??? {
??????? if(a[i]<=a[j])
??????? {
??????????? p[cnt++]=a[i];
??????????? i++;
??????? }
??????? else
??????? {
??????????? p[cnt++]=a[j];
??????????? j++;
??????????? ans+=mid-i+1;//第i个比j大 由于i已经从小到大排过序了 那么i+1到mid的也会比j大
??????? }
??? }
??? while(i<=mid)
??? {
??????? p[cnt++]=a[i++];
??? }
??? while(j<=right)
??? {
??????? p[cnt++]=a[j++];
??? }
??? cnt=0;
??? for(i=left;i<=right;i++)
??????? a[i]=p[cnt++];
??? free(p);

}
void merge_sort(int left,int right)
{
??? if(left ??? {
??????? int mid;
??????? mid=(left+right)/2;
??????? merge_sort(left,mid);
??????? merge_sort(mid+1,right);
??????? merge(left,mid,right);
??? }
}

int main()
{
??? int n,i,j ;
??? while(scanf("%d",&n)!=EOF)
??? {

??? for(i=0;i ??????? ans=0;
??????? merge_sort(0,n-1);
??????? //printf("ans=%d\n",ans);
??????? int cnt=999999999;
??????? if(cnt>ans) cnt=ans;

?????????? for(i=0;i ?????????? {
?????????????? //printf("a[i]=%d\n",a[i]);
?????????????? ans=ans-b[i]+n-1-b[i];
?????????????? if(cnt>ans)? cnt=ans;
??????????? }
?????????? printf("%d\n",cnt);
??? }
??? return 0;
}

?