// https://www.geeksforgeeks.org/inversion-count-in-array-using-merge-sort/
// C++ program to Count Inversions in an array using merge sort

#include <iostream>
#include <vector>
using namespace std;

// Fonction pour fusionner deux tableaux arr[left ... middle] et arr[middle + 1 ... right]
// et compter le nombre d'inversions dans arr[left ... right]
int countAndMerge(vector<int> &arr, int left, int middle, int right)
{
	// Tailles de chaque tableau :
	int n1 = middle - left + 1, n2 = right - middle;

	// Création de deux tableaux temporaires :
	vector<int> gauche(n1), droite(n2);
	for(int i = 0; i < n1; i++)
		gauche[i] = arr[i + left];
	for(int j = 0; j < n2; j++)
		droite[j] = arr[middle + 1 + j];

	// Initialisation et fusion des deux sous-tableaux :
	int res = 0;
	int i = 0, j = 0, k = left;
	while(i < n1 && j < n2)
	{
		// Aucune incrémentation du compteur d'inversions
		// si gauche[i] est <= droite[j] :
		if(gauche[i] <= droite[j]) 
		{
			arr[k++] = gauche[i++];
		}
		else
		{
			// Si droite[j] est <= gauche[i], alors droite[j] <= (n1 - i) éléments
			// car gauche[] est trié :
			arr[k++] = droite[j++];
			res += (n1 - i);
		}
	}

	// Fusion des éléments restants :
	while(i < n1)
		arr[k++] = gauche[i++];
	while(j < n2)
		arr[k++] = droite[j++];

	return res;
} // countAndMerge()

// Fonction pour compter le nombre d'inversions dans un tableau :
int countInv(vector<int> &arr, int left, int right)
{
	int res = 0;
	if(left < right)
	{
		int mid = (right + left) / 2;

		// Appels récursifs pour les sous-tableaux gauche et droit :
		res += countInv(arr, left, mid);
		res += countInv(arr, mid + 1, right);

		// Compte du nombre d'inversions telles que le plus grand élément est dans
		// le sous-tableau gauche et le plus petit dans le sous-tableau droit :
		res += countAndMerge(arr, left, mid, right);
	}
	return res;
} // countInv()

int inversionCount(vector<int> &arr)
{
	return countInv(arr, 0, arr.size() - 1);
} // inversionCount()

int main()
{
	vector<int> arr = {4, 3, 2, 1};

	cout << inversionCount(arr) << '\n';

	return 0;
} // main()