http://poj.org/problem?id=2299
#include<iostream>
using namespace std;
int aa[500010],bb[500010];
long long s=0;
void merge(int l,int m,int r)
{
int i=l,j=m+1,t=0;
while(i<=m&&j<=r)
{
if(aa[i]>aa[j])
{
bb[t++]=aa[j++];
s+=m-i+1;
}
else
{
bb[t++]=aa[i++];
}
}
while(i<=m)
bb[t++]=aa[i++];
while(j<=r)
bb[t++]=aa[j++];
for(int i=0;i<t;i++)
{
aa[l+i]=bb[i];
}
}
void Msort (int L,int R)
{
int cen;
if(L<R)
{ cen=(L+R)/2;
Msort(L,cen);
Msort(cen+1,R);
merge(L,cen,R);
}
}
void merge_sort(int *a,int n)
{ Msort(0,n-1);
}
int main()
{
int n;
while(cin>>n)
{
if(n==0)break;
for(int i=0;i<n;i++)
{
cin>>aa[i];
}
merge_sort(aa,n);
cout<<s<<endl;
s=0;
}
return 0;
}