分三种情况：

1. 逆序对都在左半边
2. 逆序对都在右半边
3. 在左右两侧。

第三种情况是最难。这里的解决方案是：

两边都已经有序了。但是左半边和右半边无序。一旦发现左半边里和右半边里有一个逆序对，那就说明左半边这个元素直到左半边的右边界 mid全是逆序对。

#include <iostream>

using namespace std;

const int N = 100010;
typedef long long LL;

int a[N], tmp[N];

LL merge_sort(int l, int r ) {
    if (l >= r) return 0;
    int mid = (l + r ) >> 1;
    LL res = merge_sort(l, mid ) + merge_sort(mid + 1, r );
  
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j] ) tmp[k ++] = a[i ++];
        else {
            tmp[k ++ ] = a[j ++];
            res += mid - i + 1;
            // 因为i那部分（左半边）已经是有序的了。既然a[i]已经是逆序对了，那在i后面的直到mid也都是逆序对
            // 所以直接加上这段长度就行了
        }
    }
  
    // 扫尾
    while (i <= mid ) tmp[k ++] = a[i ++];
    while (j <= r ) tmp[k ++ ] = a[j ++];
    for (i = l, j = 0; i <= r; i ++, j ++ ) a[i] = tmp[j];
    return res;
}

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