MergeSort

#include <cmath>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::max;
using std::min;
using std::string;
using std::vector;

int inv = 0;

vector<int> MergeSort(vector<int> ar) {
  int len = ar.size();
  if (len == 1) {
    return ar;
  }
  vector<int> lt;
  vector<int> rt;
  for (int id = 0; id < len / 2; ++id) {
    lt.push_back(ar[id]);
  }
  for (int id = len / 2; id < len; ++id) {
    rt.push_back(ar[id]);
  }
  lt = MergeSort(lt);
  rt = MergeSort(rt);
  int ln = lt.size();
  int rn = rt.size();
  int lid = 0;
  int rid = 0;
  vector<int> res;
  while (lid < ln || rid < rn) {
    if (lid < ln && rid < rn) {
      if (lt[lid] <= rt[rid]) {
        res.push_back(lt[lid]);
        lid++;
      } else {
        res.push_back(rt[rid]);
        rid++;
        inv += ln - lid;
      }
    } else if (lid < ln) {
      res.push_back(lt[lid]);
      lid++;

    } else if (rid < rn) {
      res.push_back(rt[rid]);
      rid++;
    }
  }
  return res;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  int len;
  cin >> len;
  vector<int> ar(len);
  for (int& el : ar) {
    cin >> el;
  }
  ar = MergeSort(ar);
  /*for (int el: ar) {
    cout << el << ' ';
  }
  cout << "\n";*/
  cout << inv << "\n";
}