class Solution {
    public int inversePairs(int[] nums) {
        return merge_sort(nums,0,nums.length-1);
    }
    private int merge_sort(int []nums,int l,int r){
        if(l>=r) return 0;
        int mid=l+(r-l)/2;
       int res=merge_sort(nums,l,mid)+merge_sort(nums,mid+1,r);
        int temp[]=new int[r-l+1];
        int i=l,j=mid+1;
        for(int k=0;k<r-l+1;k++){
            if(i>mid){
                temp[k]=nums[j++];
                continue;
            }
            if(j>r){
                temp[k]=nums[i++];
                continue;
            }
            if(nums[i]<=nums[j]){
                temp[k]=nums[i++];
            }
            else {
                res+=mid-i+1;
                temp[k]=nums[j++];
            }
        }
        for(int k=0;k<r-l+1;k++) nums[l+k]=temp[k];
        return res;
    }
}