/**
Задача: насчитать invL[i]
		насчитать invR[i]
		inv = \sum_i invL[i] = \sum_i invR[i]
		
Задача 2: 3-инверсии
		\sum_j invL[j] * invR[j]
*/

int inv = 0;
// исходно a[i] = {значение, i}
void MSort( int n, pair<int,int> *a, int *buffer ) {
	if (n <= 1) return;
	int m = n / 2;
	MSort(m, a, buffer);
	MSort(n - m, a + m, buffer);
	
	int i = 0, j = m; // i=[0,m) j=[m,n)
	for (int k = 0; k < n; k++)
		if (j == n || (i < m && a[i] <= a[j]))
			// Если все элементы различны!
			invR[a[i].second] += j - m, buffer[k] = a[i++];
		else
			invL[a[j].second] += m - i, buffer[k] = a[j++];
	
	copy(buffer, buffer + n, a);
}