Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where 0 &lt;= i &lt; j &lt; nums.length and nums[i] &gt; 2 * nums[j].

&nbsp;
Example 1:
Input: nums = [1,3,2,3,1]
Output: 2
Example 2:
Input: nums = [2,4,3,5,1]
Output: 3

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 5 * 104
	-231 &lt;= nums[i] &lt;= 231 - 1


from sortedcontainers import SortedList
class Solution:
    """
    For each sub array nums[0, i]
    We sum the reverse pairs count
    of x, s.t x in [0, i-1] and nums[x] >= 2 * nums[i] + 1 
    Using a BST(sortedList) to get logN insert and lookup time.
    Time: O(NlogN)
    Space: O(N)
    """
    def reversePairs(self, nums: List[int]) -> int:
        res = 0
        bst = SortedList()
        for e in nums:
            res += len(bst) - bst.bisect_left(2 * e + 1) # the count is the N - index
            bst.add(e) # add the the bst
        return res
class Solution {
    int cnt;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        cnt = 0;
        sort(0 , n - 1 , nums);
        return cnt;
    }
    void sort(int l , int r , int nums[]){
        if(l == r){
            return;
        }
        int mid = l + (r - l) / 2;
        sort(l , mid , nums);
        sort(mid + 1 , r , nums);
        merge(l , mid , r , nums);
    }
    void merge(int l , int mid , int r , int nums[]){
        int n1 = mid - l + 1;
        int n2 = r - mid;
        int a[] = new int[n1];
        int b[] = new int[n2];
        for(int i = 0; i < n1; i++){
            a[i] = nums[l + i];
        }
        for(int j = 0; j < n2; j++){
            b[j] = nums[mid + 1 + j];
            int idx = upperBound(a , 0 , n1 - 1 , 2L * (long)b[j]);
            if(idx <= n1) {
                cnt += n1 - idx;
            }
        }
        int i = 0;
        int j = 0;
        int k = l;
        while(i < n1 && j < n2){
            if(b[j] <= a[i]){
                nums[k++] = b[j++];
            }
            else{
                nums[k++] = a[i++];
            }
        }
        while(i < n1){
            nums[k++] = a[i++];
        }
        while(j < n2){
            nums[k++] = b[j++];
        }
    }
    int upperBound(int a[] , int l , int r , long x){
        int ans = r + 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if((long)a[mid] > x){
                ans = mid;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        return ans;
    }
}
class Solution {
public:

    int merge_count(vector<int> &nums,int s,int e){
        int i;
        int mid = (s+e)/2;
        int j=mid+1;
        long long int count=0;
        for(i=s;i<=mid;i++){
            while((j<=e)&&((double)nums[i]/2.0)>nums[j]){
                j++;
            }
            count += j-(mid+1);
        }
        i=s;j=mid+1;
        vector<int> ans;
        while((i<=mid)&&(j<=e)){
            if(nums[i]<=nums[j]){
                ans.push_back(nums[i]);
                i++;
            }
            else{
                ans.push_back(nums[j]);
                j++;
            }
        }
        while(i<=mid){
            ans.push_back(nums[i]);
            i++;
        }
        while(j<=e){
            ans.push_back(nums[j]);
            j++;
        }
        for(int k=s;k<=e;k++){
            nums[k]=ans[k-s];
        }
        return count;
    }

    int reverse_count(vector<int> &nums,int s,int e){
        if(s>=e){
            return 0;
        }
        int mid = (s+e)/2;
        int l_count = reverse_count(nums,s,mid);
        int r_count = reverse_count(nums,mid+1,e);
        int s_count = merge_count(nums,s,e);
        return (l_count+r_count+s_count);
    }

    int reversePairs(vector<int>& nums) {
        int res = reverse_count(nums,0,nums.size()-1);
        return res;
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
  
    let ans = mergeSort(nums,0,nums.length-1);
    return ans;
  
    
};

var mergeSort = function(nums,l,h){
    if(l>=h){
        return 0;
    }
    let m = Math.floor((l+h)/2);
    let inv = mergeSort(nums,l,m);
    inv = inv + mergeSort(nums,m+1,h);
    inv = inv + merge(nums,l,m,h);
    return inv;
}

var merge = function (nums,l,m,h){
    let cnt = 0;
    let j=m+1;
    for(let i=l;i<=m;i++){
        while(j<=h && nums[i]> 2*nums[j]){
            j++;
        }
        cnt = cnt+(j-(m+1));
    }
    
    let left = l, right=m+1,temp=[];
    while(left<=m && right<=h){
        if(nums[left]<=nums[right]){
            temp.push(nums[left]);
            left++;
        }
        else{
            temp.push(nums[right]);
            right++;
        }
    }
    while(left<=m){
        temp.push(nums[left]);
        left++;
    }
    while(right<=h){
        temp.push(nums[right]);
        right++;
    }
    for(let i=l;i<=h;i++){
        nums[i]=temp[i-l];
    }
    return cnt;
    
}
Reverse Pairs