#include "shoes.h"
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 1e5 + 10;
#include <vector>
#define INF 0x3f3f3f3f
long long merge_sort(vector<int> &v){
long long inv=0;
if(v.size()==1) return 0;
vector<int> u1, u2;
for(int i=0;i<(int)v.size()/2;i++){
u1.push_back(v[i]);
}
for(int i=v.size()/2;i<(int)v.size();i++){
u2.push_back(v[i]);
}
inv+=merge_sort(u1);
inv+=merge_sort(u2);
u1.push_back(INF);
u2.push_back(INF);
int ini1=0, ini2=0;
for(int i=0;i<(int)v.size();i++){
if(u1[ini1]<=u2[ini2]){
v[i]=u1[ini1];
ini1++;
}
else{
v[i]=u2[ini2];
ini2++;
inv+=u1.size()-ini1-1;
}
}
return inv;
}
long long count_swaps(std::vector<int> s) {
int n = s.size();
vector< queue<int> > mapa(2*n);
vector<int> pos(n), val(n);
for (int i = 0; i < (int)s.size(); i++) {
if (!mapa[ n - s[i] ].empty()) {
int x = mapa[ n - s[i] ].front();
mapa[n - s[i]].pop();
pos[i] = x;
pos[x] = i;
}else mapa[ n + s[i] ].push(i);
}
int k = 1;
for (int i = 0; i < (int)s.size(); i++) {
if (val[ pos[i] ]){
val[i] = val[ pos[i] ] + 1;
if (s[i] < s[pos[i]])
swap(val[i], val[pos[i]]);
}
else val[i] = k, k += 2;
}
long long sum = merge_sort(val);
// for(auto & e : val)
// cout << e << " ";
// cout << "\n";
return sum;
}
