#include "shoes.h"
#include <iostream>
#include <iterator>
#include <unordered_map>
using namespace std;
using ll = signed long long int;
ll merge_sort(vector<int>& a) {
if(a.size() == 1) return 0;
vector<int> l(a.size()/2), r(a.size() - a.size()/2);
copy(a.begin(), a.begin() + a.size()/2, l.begin());
copy(a.begin() + a.size()/2, a.end(), r.begin());
ll ans = merge_sort(l) + merge_sort(r);
int i = 0, j = 0;
while(i < (int)l.size() && j < (int)r.size()) {
if(l[i] <= r[j]) a[i+j] = l[i], i++;
else ans += l.size() - i, a[i+j] = r[j], j++;
}
while(i < (int)l.size()) a[i+j] = l[i], i++;
while(j < (int)r.size()) a[i+j] = r[j], j++;
return ans;
}
long long count_swaps(std::vector<int> a) {
int n = a.size(), x = 0;
vector<int> idx(n);
unordered_map<int, int> pairs;
for(int i = 0; i < n; ++i) {
int gr = abs(a[i]) >> 1;
if(pairs.count(gr)) {
idx[i] = pairs[gr] + (a[i] > 0);
pairs.erase(gr);
} else {
idx[i] = x + (a[i] > 0);
pairs[gr] = x;
x += 2;
}
}
return merge_sort(idx);
}
