#include
using namespace std;
void merge(int a, int s, int e)
{
int mid = (s+e) / 2;
int i = s;
int j = mid+1;
int temp [10000];
int cnt = 0;
int k = s;
while(i <= mid and j<=e)
{
if(a[i] <= a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k++] = a[j++];
cnt+ = mid - i + 1;
}
}
while(i<=mid)
{
temp[k++] = a[i++]
}
while(j<=e)
{
temp[k++] = a[j++];
}
for(int i = s; i<=e ; i++)
{
a[i] = temp[i];
}
return cnt;
}
void inversion(int *a , int s, int e)
{
if(s>=e)
{
return 0;
}
int mid = (s + e) / 2;
int x = inversion(a,s,mid);
int y = inversion(a,mid+1,e);
int z = merge(a,s,e);
return x+y+z;
}
main()
{
int a[] = {1,5,2,6,3,0}
int n = sizeof(a) / sizeof(int);
cout<<inversion(a,0,n);
}