#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include "shoes.h"
using namespace std;
typedef long long ll;
vector<ll> t;
ll getSum(ll idx){
ll sum = 0;
idx++;
while (idx > 0){
sum += t[idx];
idx -= idx & (-idx);
}
return sum;
}
void updateF(ll n, ll idx, ll val){
idx++;
while (idx <= n){
t[idx] += val;
idx += idx & (-idx);
}
}
ll count_swaps(vector<int> s){
ll n = s.size()/2;
t.assign(2*n + 1, 0);
vector<queue<ll>> cnt1(n + 1, queue<ll> ()), cnt2(n + 1, queue<ll> ());
queue<ll> q;
for (ll i = 2*n - 1; i >= 0; i--){
if (s[i] < 0)
cnt2[-s[i]].push(i);
else
cnt1[s[i]].push(i);
}
vector<bool> koristen(2*n, false);
ll res = 0;
ll pocetak = 2*n - 2;
for (int i = 2*n - 1; i >= 0; i--){
if (koristen[i])
continue;
ll curr = i, par;
if (s[i] < 0){
res++;
par = cnt1[-s[i]].front();
cnt1[-s[i]].pop();
cnt2[-s[i]].pop();
}
else{
par = cnt2[s[i]].front();
cnt1[s[i]].pop();
cnt2[s[i]].pop();
}
koristen[curr] = true; koristen[par] = true;
par += getSum(par);
res += pocetak - par;
updateF(2*n, par, -1);
pocetak -= 2;
}
return res;
}
