逆序对

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100010], t[100010];
long long ans = 0;
void merge_sort(int* a, int x, int y, int* t){
	if (y - x > 1){
		int m = x + (y - x) / 2;
		int p = x, q = m, i = x;
		merge_sort(a, x, m, t);
		merge_sort(a, m, y, t);
		while (p < m || q < y)
		    if (q >= y || (p < m && a[p] < a[q])) t[i++] = a[p++];
		    else t[i++] = a[q++], ans += m - p;
        for (int j = x; j < y; j++) a[j] = t[j];
	}
}
int main(){
	int n; cin>>n;
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	merge_sort(a, 0, n, t);
	cout<<ans;
	return 0;
}