class Solution
{
    // arr[]: Input Array
    // N : Size of the Array arr[]
    //Function to count inversions in the array.
    static long inversionCount(long arr[], long n)
    {
        long p = conqur (arr, 0, n - 1, n);
        return p;
    }
//   static long devide(long a[],long l,long r){
//          long p=0;
//          if(l<=r){
//       long mid=l+(r-l)/2;
//      p+=devide(a,l,mid);
//      p+=    devide(a,mid+1,r);
//     p+=   conqur(a,l,mid,r);
//          }
//           return p;
//     }
    static long  conqur(long a[], long l, long r, long n)
    {

        long mid = (l + r) / 2;
        long ans = 0;
        long indx1 = l, indx2 = mid + 1;
        if (l < r)
        {
            long []aa= new long[(int)(r-l+1)];
            ans += conqur(a, l, mid, n);
            ans += conqur(a, mid + 1 , r, n);
            long x=0;
            while (indx1 <= mid && indx2 <= r) {
                if (a[(int)indx1] <= a[(int)indx2]) {

                    aa[(int)x++] = a[(int)indx1++];
                } else {
                    ans += mid - indx1 + 1;
                    aa[(int)x++] = a[(int)indx2++];

                }
            }
            while (indx1 <= mid) {
                aa[(int)x++] = a[(int)indx1++];
            }
            while (indx2 <= r) {
                aa[(int)x++] = a[(int)indx2++];
            }
            x=0;
            for(long i=l;i<=r;i++){
             a[(int)i]=aa[(int)x++];
            }

        }
        return ans;
    }
}