// 双倍逆序对问题，同样可以用递归分治的思想，这个问题是否可以被分为，左半边，右半边，跨左右，排序后会不会好做

//https://leetcode.cn/problems/reverse-pairs/

class Solution {
public:
    int n;
    int help[50050];

    long long marge(vector<int>& arr , int left , int right , int mid ){
        long long ans = 0;
        for(int i=left,j=mid+1;i<=mid;i++){
            while(j<=right && (long long)arr[i]>(long long)arr[j]*2) j++;
            ans += (j-(mid+1));
        }
        int l = left , r = mid+1 , k = left;
        while(l<=mid && r <= right){
            if(arr[l] <= arr[r]){
                help[k++] = arr[l++];
            }else{
                help[k++] = arr[r++];
            }
        }
        while(l <= mid) help[k++] = arr[l++];
        while(r <= right) help[k++] = arr[r++];

        for(l=left;l<=right;l++) arr[l] = help[l];
        return ans;
    }

    long long marge_sort(vector<int>& nums , int left , int right){
        if(left >= right) return 0;
        int mid = (left+right)/2;
        return marge_sort(nums,left,mid)+marge_sort(nums,mid+1,right)+marge(nums,left,right,mid);
    }
    int reversePairs(vector<int>& nums) {
        n = nums.size();
        long long ans = marge_sort(nums,0,n-1);
        return ans; 
    }
};