#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<int> st;
void tog(int pos, int node=1, int tl=0, int tr=2*n-1){
if (tl == tr){
st[node] = 1;
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) tog(pos, node*2, tl, tm);
else tog(pos, node*2+1, tm+1, tr);
st[node] = st[node*2]+st[node*2+1];
}
int query(int l, int r, int node=1, int tl=0, int tr=2*n-1){
if (l <= tl && tr <= r) return st[node];
int tm = (tl+tr)/2;
int res = 0;
if (l <= tm) res += query(l, r, node*2, tl, tm);
if (tm+1 <= r) res += query(l, r, node*2+1, tm+1, tr);
return res;
}
ll count_swaps(vector<int> s){
n = s.size()/2;
map<int,queue<int>> m;
for (int i=0; i<2*n; i++) m[s[i]].push(i);
ll res = 0;
vector<bool> done(2*n, false);
st.resize(8*n, 0);
for (int i=0; i<2*n; i++){
if (done[i]) continue;
int j = m[-s[i]].front();
m[-s[i]].pop();
m[s[i]].pop();
res += j-i;
res -= query(i, j);
if (s[i] < 0) res--;
done[j] = true;
tog(j);
}
return res;
}
