快速排序模板题，要注意结果会超过Int， 要使用long long。 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int a[100005];
ll cnt = 0;
void Merge(int l1, int r1, int l2, int r2) {
    int temp[100005], begin=l1, i=0;
    while (l1<=r1&&l2<=r2) {
        if (a[l1]<=a[l2]) {
            temp[i++] = a[l1++];
        } else {
            temp[i++] = a[l2++];
            cnt+=r1-l1+1;
        }
    }
    while (l1<=r1) temp[i++] = a[l1++];
    while (l2<=r2) temp[i++] = a[l2++];
    for (int j=0;j<i;j++) {
        a[begin+j] = temp[j];
    }
}

void find_inv_num(int l, int r) {
    if (l==r) return ;
    int mid = (l+r)/2;
    find_inv_num(l, mid);
    find_inv_num(mid+1, r);
    Merge(l, mid, mid+1, r);
}

int main() {
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    find_inv_num(1, n);
    cout<<cnt;
    return 0;
}