Code: Select all
#include<bits/stdc++.h>
using namespace std;
long long cnt=0;
void merge(int *A,int *L,int *R,int ln,int rn)
{
int i=0,j=0,k=0;
while(i<ln&&j<rn)
{
if(L[i]<=R[j])
A[k++]=L[i++];
else
{
A[k++]=R[j++];
cnt+=ln-i;
}
}
while(j<rn)A[k++]=R[j++];
while(i<ln)A[k++]=L[i++];
}
void mergesort(int *A,int n)
{
int i;
if(n<2)
return;
int mid=n/2;
int left[mid+5],right[n-mid+5];
for(i=0; i<mid; i++)
left[i]=A[i];
for(i=mid; i<n; i++)
right[i-mid]=A[i];
mergesort(left,mid);
mergesort(right,n-mid);
merge(A,left,right,mid,n-mid);
free(left);
free(right);
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("out.txt","w",stdout);
int i,j,n,temp;
while(scanf("%d",&n)==1)
{
cnt=0;
int arr[n+5];
if(n==0)
break;
for(i=0; i<n; i++)
{
cin >>arr[i];
}
mergesort(arr,n);
cout <<cnt<<endl;
}
return 0;
}