// Èíâåðñèÿ: (i, j) : i < j, a[i] > a[j]

const int N = (int)1e6;

int b[N];
int inv_l[N];

// Java : l, r, a
void MSort( int n, int *a )
{
  if (n <= 1)
    return;

  int m = n / 2;
  MSort(m, a);
  MSort(n - m, a + m);

  // [0, m) [m, n) --> [0, n)
  // äëÿ ëþáûõ i != j : a[i] != a[j]
  // a[i] = 1..n  
  int i = 0, j = m;
  for (int k = 0; k < n; k++)
    if (i < m && (j == n || a[i] < a[j]))
      b[k] = a[i++];
    else
      b[k] = a[j], inv_l[a[j++]] += m - i; // [i, m) a[i]..a[m - 1] > a[j]

  for (int k = 0; k < n; k++)
    a[k] = b[k];
}

// j : inv_l[j] = êîë-âî i, ÷òî i < j, a[i] > a[j]
// j : inv_r[j] = êîë-âî i, ÷òî i > j, a[i] < a[j]