LSD_v4

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

using std::cin;
using std::cout;
using std::max;
using std::min;
using std::string;
using std::vector;
using ll = long long;

int inv = 0;

vector<vector<string>> MergeSort(vector<vector<string>> ar, int par) {
  int len = ar.size();
  if (len == 1) {
    return ar;
  }
  vector<vector<string>> lt;
  vector<vector<string>> 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, par);
  rt = MergeSort(rt, par);
  int ln = lt.size();
  int rn = rt.size();
  int lid = 0;
  int rid = 0;
  vector<vector<string>> res;
  while (lid < ln || rid < rn) {
    if (lid < ln && rid < rn) {
      if (lt[lid][par] <= rt[rid][par]) {
        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;
}

string Bin(ll num) {
    string st = "";
    while (num > 0) {
      st += std::to_string(num % 2);
      num /= 2;
    }
    while ((int)st.size() < 64) {
      st += '0';
    }
    return st;
}

vector<string> Get(string st) {
  vector<string> res;
  for (int id = 0; id < 64; id += 8) {
    string add = st.substr(id, 8);
    res.push_back(add);
  }
  return res;
}

ll from(vector<string> vec) {
  string st = "";
  for (int id = 0; id < 8; ++id) {
    st += vec[id];
  }
  /*cout << "from\n";
  cout << "st\n";
  cout << st << "\n";*/
  ll res = 0;
  for (int id = 0; id < 64; ++id) {
    ll add = (ll)(st[id] - '0') * pow(2LL, id);
    //cout << "id = " << id << "\n";
    //cout << "add = " << add << "\n";
    res += add;
  }
  return res;
}


int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  /*
  ll kk;
  cin >> kk;
  string st = Bin(kk);
  //cout << st << "\n";
  vector<string> vec = Get(st);
  for (int id = 0; id < 8; ++id) {
    cout << vec[id] << ' ';
  } cout << "\n";
  */
  /*ll num;
  cin >> num;
  string st = Bin(num);
  cout << st << "\n";
  vector<string> vec = Get(st);
  for (string st: vec) {
    cout << st << ' ';
  }
  cout << "\n";
  ll cmp = from(vec);
  cout << cmp << "\n";*/
  /*int len;
  cin >> len;
  vector<vector<string>> ar;
  for (int id = 0; id < len; ++id) {
    ll num; cin >> num;
    string st = Bin(num);
    vector<string> vec = Get(st);
    ar.push_back(vec);
  }
  for (int par = 0; par < 8; ++par) {
    ar = MergeSort(ar, par);
  }
  vector<ll>res;
  for (int id = 0; id < len; ++id) {
    ll num = from(ar[id]);
    res.push_back(num);
  }
  for (int id = 0; id < len; ++id) {
    cout << res[id] << "\n";
  }
  cout << "\n";*/
}
/*
9223372036854775807

111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111110

*/