给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
1≤n≤100000
输入样例：
6
2 3 4 5 6 1
输出样例：
5

思路：
我们将序列从中间分开，将逆序对分成三类：

两个元素都在左边；
两个元素都在右边；
两个元素一个在左一个在右；
因此这就是我们算法的大致框架：

计算逆序对的数量（序列）：

1. 递归算左边的；
2. 递归算右边的；
3. 算一个左一个右的；
4. 把他们加到到一起。
5. 设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8，1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11,；

逆序数为14；

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 100010;
int q[N],tmp[N];

int merge_sort(int q[], int l, int r)
{
    if(l >= r)
    return 0;
    int mid = (r+l) / 2;
    int i = l, j = mid + 1;
    int k = 0;
    ll res = merge_sort(q,l,mid) + merge_sort(q,mid+1,r);
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j])
        tmp[k++] = q[i++];
        else
        {
            tmp[k++] = q[j++];
            res += mid - i + 1;
        }
    }
    while(i <= mid)
    tmp[k++] = q[i++];
    while(j <= r)
    tmp[k++] = q[j++];
    for(int i = l, j = 0; i <= r; i++, j++)
    q[i] = tmp[j];
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    scanf("%d",&q[i]);
    printf("%ld",merge_sort(q,0,n - 1));
    return 0;
}