CountInversion

import java.util.* ;
import java.io.*; 
public class Solution {
    public static long getInversions(long nums[], int n) {
        Long[] count = new Long[1];
        count[0] = 0l;
        mergeSort(nums,0,n-1,count);
        return count[0];
    }
    private static void mergeSort(long[] nums,int start,int end,Long[] count){
        if(start>=end) return;
        int mid = start + (end-start)/2;
        mergeSort(nums,start,mid,count);
        mergeSort(nums,mid+1,end,count);
        merge(nums,start,mid,end,count);
    }
    private static void merge(long nums[],int start,int mid,int end,Long[] count){
        long ans[] = new long[end-start+1];
        int s1 = start;
        int s2 = mid+1;
        int index = 0;
        while(s1<=mid && s2<=end){
            if(nums[s1]<=nums[s2]){
                ans[index++] = nums[s1];
                s1++;
            }else{
                ans[index++] = nums[s2];
                s2++;
                count[0] += mid-s1+1;
            }
        }
        while(s1<=mid){
            ans[index++] = nums[s1];
            s1++;
        }
        while(s2<=end){
            ans[index++] = nums[s2];
            s2++;
        }
        for(int i=0;i<ans.length;i++){
            nums[i+start] = ans[i];
        }
    }
}