发明人超级大帅童发明项目逆序对发明成功

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int a[500005], arr[500005];
int read(){
	char c = getchar();
	int x = 0;
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}return x;
}
long long merge(int *left, int *mid, int *right){
	vector <int> v(right - left + 1);
	int *i = left, *j = mid;
	int k = 0;
	long long ct = 0;
	while(i < mid && j < right){
		if(*i <= *j) v[k++] = *i++;
		else ct += mid - i, v[k++] = *j++;
	}
	while(i < mid) v[k++] = *i++;
	while(j < right) v[k++] = *j++;
	int len = right - left;
	for(int i = 0; i < len; i++){
		*left++ = v[i];
	}
	return ct;
}
long long get_inversion(int *left, int *right){
	if(left + 1 >= right) return 0;
    int *mid = left + (right - left >> 1);
	return get_inversion(left, mid) + get_inversion(mid, right) + merge(left, mid, right);
}
int main(){
	int n = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	printf("%lld", get_inversion(a + 1, a + n + 1));
	fclose(stdin);

	return 0;
}