#include <iostream>
 
using namespace std;
 
int merge(int *arr, int l, int split, int r) {
  int *buf = new int[r - l + 1];
 
  int pos1 = l;
  int pos2 = split + 1;
  int pos3 = 0;
 
  int k = 0;
  while ((pos1 <= split)&&(pos2 <= r)) {
    if (arr[pos1] < arr[pos2])
      buf[pos3++] = arr[pos1++];
    else {
      buf[pos3++] = arr[pos2++];
      k +=(split - pos1 + 1); 
    }
  }
 
  while (pos2 <= r)
    buf[pos3++] = arr[pos2++];
  while (pos1 <= split)
  { buf[pos3++] = arr[pos1++]; k++; }
 
  for (pos3 = 0; pos3 < r-l+1; pos3++)
    arr[l + pos3] = buf[pos3];
 
  delete[] buf;
  return (k);
}
 
int merge_sort(int *arr, int l, int r) {
  long split;
  int k = 0;
  if (l < r) {
    split = (l+r)/2;
    merge_sort(arr, l, split);
    merge_sort(arr, split + 1, r);
    k += merge(arr, l, split, r);
  }
  return (k);
}
 
int main(void) {
  int n = 4;
  //cin >> n;
//   int *src_bread = new int[n];
//   int *needed_br = new int[n];
//   for (int i = 0; i < n; i++)
//     cin >> src_bread[i];
//   for (int i = 0; i < n; i++)
//     cin >> needed_br[i];
 
  int src_bread[4] = {1, 3, 4, 2};
  int needed_br[4] = {4, 3, 2, 1};
 
  int k1 = merge_sort(src_bread, 0, n - 1);
  int k2 = merge_sort(needed_br, 0, n - 1);
 
  cout << "INV1: " << k1 << " INV2 = " << k2 << endl;
 
//   if (k1 % 2 != k2 % 2)
//     cout << "Impossible";
//   else cout << "Possible";
 
  int slp;
  cin >> slp;
 
  return 0;
}