/*分析:a[0]的逆序数为0,a[0]后边有a[0]个比a[0]小的数,将a[0]移到末尾是,a[0]的逆序数变成n-1-a[0];
而a[0]个比a[0]小的数的逆序数都减1,设原序列的逆序数为sum,则新序列的逆序数sum=sum-a[0]+n-1-a[0];
当m>1时,sum=sum(m-1)+n-1-a[0]-a[0];a[0]是m-1次移动后序列的首元素。
*/
#include<stdio.h> #define inf 0x3fffffff int a[5010]; int main() { int n,i,j,sum,min; while(scanf("%d",&n)!=-1) { sum=0; scanf("%d",&a[0]); for(i=1;i<n;i++) { scanf("%d",&a[i]); j=i-1; while(j>=0) { if(a[j--]>a[i]) sum++; } } min=inf; for(i=0;i<n-1;i++) { sum=sum+(n-a[i]-1)-a[i]; if(min>sum) min=sum; } printf("%d\n",min); } return 0; }