class Solution {
public:
    //归并模板。多写几次！！！
    int merge(vector<int>& nums,int l,int r){
        if(l >= r) return 0;
        int mid = l + r >> 1;
        int res = merge(nums,l,mid) + merge(nums,mid + 1,r);

        vector<int> tmp;
        int i = l,j = mid + 1;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]) tmp.push_back(nums[i++]);
            else{
                res += mid - i + 1;
                tmp.push_back(nums[j++]);
            }
        }

        while(i <= mid) tmp.push_back(nums[i++]);
        while(j <= r) tmp.push_back(nums[j++]);

        i = l;
        for(auto x:tmp)
            nums[i++] = x;
        return res;
    }


    int inversePairs(vector<int>& nums) {
       return merge(nums,0,nums.size() - 1); 
    }
};