求排列的逆序数

#include<bits/stdc++.h>
using namespace std;
#define N 100005

long long n;
long long a[N];
long long b[N];
long long ans = 0;
void merge(long long L, long long R) {
	long long mid = (L + R) / 2;
	long long l = L;
	long long r = mid+1;
	long long count = 0;
	while(l <= mid && r <= R) {
		if(a[l] < a[r]) {
			b[count++] = a[r++];
		} else {
			b[count++] = a[l++];
			ans += R - r + 1;
		}
	}
	while(l <= mid) b[count++] = a[l++];
	while(r <= R) b[count++] = a[r++];
	for(long long i = L; i <= R; i++) a[i] = b[i-L];
}
void MergeSortAndCount(long long L, long long R) {
	if(L < R) {
		long long mid = (L + R) / 2;
		MergeSortAndCount(L, mid);
		MergeSortAndCount(mid + 1, R);
		merge(L, R);
	}
}
int main() {
	cin>>n;
	for(long long i = 0; i < n; i++) {
		cin>>a[i];
	}
	MergeSortAndCount(0, n-1);
	cout << ans;
	return 0;
}