class Solution {
public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }
    
    int mergeSort(vector<int>& nums, int start, int end) {
        if (start >= end) {
            return 0;
        }
        int mid = (start + end) / 2;
        int lc = mergeSort(nums, start, mid);
        int rc = mergeSort(nums, mid + 1, end);
        int cnt = count(nums, start, mid, end);
        return lc + rc + cnt;
    } 
    
    int count(vector<int>& nums, int start, int mid, int end) {
        int l = start, r = mid + 1;
        int count = 0;
        while(l <= mid && r <= end){
            if((long)nums[l] > (long)2 * nums[r]){
                count += (mid - l + 1);
                r++;
            }else{
                l++;
            }
        }
        sort(nums.begin() + start, nums.begin() + end + 1);
        return count;
    }
};