#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
long long count_swaps(std::vector<int> s) {
long long sort_inversions = 0, total_inversions = 0;
int N = (s.size()/2), left_pair = 0, right_pair = 0, cpos;
std::vector<int> position(N), BIT(N);
std::vector<std::queue<int>> compensated_inversions(N+1, queue<int> ()), positional_queue(N+1, queue<int> ());
for(int i = 2*N-1; i>=0; i--) {
if(s[i]<0 && positional_queue[abs(s[i])].empty()) {
compensated_inversions[abs(s[i])].push(left_pair);
left_pair++;
}
else if(s[i]<0) {
position[N-1-left_pair] = N-positional_queue[abs(s[i])].front();
positional_queue[abs(s[i])].pop();
left_pair++;
}
else if(!compensated_inversions[s[i]].empty()) {
total_inversions += left_pair - compensated_inversions[s[i]].front();
right_pair++;
position[N-compensated_inversions[s[i]].front()-1] = N-right_pair;
compensated_inversions[s[i]].pop();
}
else {
right_pair++;
positional_queue[s[i]].push(right_pair);
}
}
for(int i = 0, j; i<N; i++) {
j = i+1;
while(j>0) {
BIT[j-1]++;
j -= (j & (-j));
}
}
for(int i = N-1; i>=0; i--) {
cpos = position[i] + 2;
while(cpos<=N) {
sort_inversions += BIT[cpos-1];
cpos += (cpos & (-cpos));
}
cpos = position[i] + 1;
while(cpos>0) {
BIT[cpos-1]--;
cpos -= (cpos & (-cpos));
}
}
return (total_inversions+sort_inversions);
}
