• 暴力解法：枚举 i,j,复杂度 $O(n^2)$
• 正解：利用归并排序的特点。
• 注意开 long long.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll P = 1e9 + 7;
const int N = 5e6 + 5;

int n,k, a[N], tem[N];
ll cnt=0;
void qsort(int l, int r) {  //  [l, r]  = [l, j]  + [i, r]
    if (l >= r)
        return;
    int i = l, j = r, base = a[l + r >> 1];
    while (i <= j) {  // [l,j] <= b,    [i,r] >=b
        while (a[i] < base)
            i++;
        while (a[j] > base)
            j--;
        if (i <= j)
            swap(a[i], a[j]), i++, j--;
    }
    if(k <=j) qsort(l, j);
    if(k >=i) qsort(i, r);
}
// [l, r] = [l,mid] + [mid+1, r]
void msort(int l,int r){
	if(l>=r) return;
	int mid =l +r >> 1;
	msort(l,mid);
	msort(mid+1, r);
	
	int i=l, j=mid+1, p=0;
	while(i<=mid && j<=r){
		if(a[i] <= a[j]) tem[++p] = a[i++];
		else tem[++p] = a[j++], cnt += mid-i+1;
	}
	while(i <= mid) tem[++p] = a[i++];
	while(j <= r) tem[++p] = a[j++];
	for(int i=1; i<=p; i++) a[l++]=tem[i];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    msort(0, n-1);
    printf("%lld", cnt);
    return 0;
}