#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>> cnt(n + 1, queue<ll> ());
queue<ll> q;
vector<pair<int, int>> koristen(n + 1, make_pair(0, 0));
for (ll i = 2*n - 1; i >= 0; i--){
if (s[i] < 0){
if (koristen[-s[i]].first > 0){
cnt[-s[i]].push(-(i + 1));
koristen[-s[i]].first--;
}
else{
q.push(i);
koristen[-s[i]].second++;
}
}
else{
if (koristen[s[i]].second > 0){
cnt[s[i]].push(i + 1);
koristen[s[i]].second--;
}
else{
q.push(i);
koristen[s[i]].first++;
}
}
}
ll res = 0;
ll pocetak = 2*n - 2;
while(!q.empty()){
ll curr = q.front();
ll par = cnt[abs(s[curr])].front();
q.pop(); cnt[abs(s[curr])].pop();
if (par > 0)
res++;
else
par = -par;
par--;
par += getSum(par);
curr += getSum(curr);
res += pocetak - par;
updateF(2*n, par, -1);
pocetak -= 2;
}
return res;
}
