#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

pair<vector<int>, int> merge(vector<int> &a, int ll, int rl, int lr, int rr) {
	vector<int> res;
	int inv = 0;
	int l1 = ll;
	int r1 = lr;
	while(l1 <= rl && r1 <= rr) {
		if(a[l1] < a[r1]){
			res.push_back(a[l1]);
			l1++;
		} else {
			res.push_back(a[r1]);
			r1++;
			inv = inv + lr - l1;
		}
	}
	for(int i = r1; i <= rr; i++)
		res.push_back(a[i]);
	for(int i = l1; i <= rl; i++)
		res.push_back(a[i]);
	return {res, inv};
}

int inv(vector<int> &a, int l, int r) {
	if (r-l < 1)
		return 0;
	auto li = inv(a, l, (l+r)/2); 
	auto ri = inv(a, (l+r)/2+1, r);
	auto res = merge(a, l, (l+r)/2, (l+r)/2+1, r);
	for(int i = l, idx = 0; i <= r; i++, idx++) {
		a[i] = res.first[idx];
	}
	return li + ri + res.second;
}

int32_t main(){
	vector<int> a = {5, 1, 2, 3, 4, 0};
	cout << inv(a, 0, a.size() - 1);
	return 0;
}