描述：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。给你一个数组，求出这个数组中逆序对的总数。
概括：如果a[i] > a[j] 且 i < j， a[i] 和 a[j] 构成一个逆序对。
思路：归并排序，在每次递归调用中，先对左半部分排序，然后统计右半部分每个值在左半部分的逆序对数

class Solution {
public:
    /**
     * @param A: an array
     * @return: total of reverse pairs
     */
    long long reversePairs(vector<int> &A) {
        // write your code here
        int ans = 0;
        int len = A.size();
        ans = DFS(A,0,A.size());
        return ans;
    }
    int DFS(vector<int> &A,int left,int right)
    {
        if( right - left <= 1)
        {
            return 0;
        }
        int mid = (left + right) >> 1;
        int res = DFS(A,left,mid) + DFS(A,mid,right);
        sort(A.begin() + left,A.begin() + mid);
        for( int i = mid;i < right; ++i )
        {
            res += A.begin() + mid - std::upper_bound(A.begin() + left,A.begin() + mid,A[i]);
        }
        return res;
    }