Problem Description

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

线段树功能：单点增减，区间求和。

#include
       
         int v[5001]; typedef struct {
     int left; int right; int mid; int tot; }line; line l[20004]; void creat(int a,int b,int r) {
         l[r].left=a;     l[r].right=b;     l[r].tot=0;     l[r].mid=(a+b)>>1; if(a==b) return;     creat(a,l[r].mid,r<<1);     creat(l[r].mid+1,b,(r<<1)+1); } void update(int a,int b,int r) {
     if(l[r].left>b||l[r].right
        
         =a&&l[r].right<=b)     {
             l[r].tot+=1; return;     }     update(a,b,r<<1);     update(a,b,(r<<1)+1);     l[r].tot=l[r<<1].tot+l[(r<<1)+1].tot; } int query(int a,int b,int r) {
     if(l[r].left>b||l[r].right
         
          =a&&l[r].right<=b) return l[r].tot; return  query(a,b,r<<1)+query(a,b,(r<<1)+1); } int main() {
     int res,sum,n,i; while(scanf("%d",&n)!=EOF)     {
             creat(1,n,1);         sum=0; for(i=0;i
         
        
       

方法二：树状数组

#include
       
         #include
        
          #define min(a,b)(a)<(b)?(a):(b); int v[5002]; int l[5002]; int n; int lowbit(int x) {
     return (x)&(-x); } void update(int pos) {
     while(pos<=n)     {
             l[pos]+=1;         pos+=lowbit(pos);     } } int getsum(int x) {
     int sum=0; while(x>0)     {
             sum+=l[x];         x-=lowbit(x);     } return sum; } int main() {
     int res,p,i,sum; while(scanf("%d",&n)!=EOF)     {
             sum=0;         memset(l,0,sizeof(l)); for(i=0;i