#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;
struct fenwick{
int n;
vector<int> fen;
fenwick(int n) : n(n), fen(n){}
void upd(int pos, int val){
for(; pos < n; pos |= pos + 1)
fen[pos] += val;
}
int index(int ind){
int ret = 0;
for(; ind >= 0; ind = (ind & (ind + 1)) - 1)
ret += fen[ind];
return ret;
}
};
ll count_swaps(vector<int> v){
int n = v.size() / 2;
vector<vector<int>> a(n * 2 + 1);
for(int i = 2 * n - 1; i >= 0; i--){
a[v[i] + n].pb(i);
}
fenwick fen(2 * n);
for(int i = 0; i < 2 * n; i++){
fen.upd(i, 1);
}
ll ans = 0;
vector<int> el(2 * n);
for(int i = 0; i < 2*n; i++){
while(i < 2 * n && fen.index(i) == 0) i++;
if(i == 2 * n) break;
if(v[i] < 0){
fen.upd(i, -1);
int nxt = a[-v[i] + n].back(); a[-v[i] + n].pop_back();
while(el[nxt]){
nxt = a[-v[i] + n].back(); a[-v[i] + n].pop_back();
}
int ind = fen.index(nxt);
ans += ind - 1;
fen.upd(nxt, -1);
el[nxt] = el[i] = 1;
}
else{
int nxt = a[-v[i] + n].back(); a[-v[i] + n].pop_back();
while(el[nxt]){
nxt = a[-v[i] + n].back(); a[-v[i] + n].pop_back();
}
fen.upd(i, -1);
int ind = fen.index(nxt);
ans += ind;
fen.upd(nxt, -1);
el[nxt] = el[i] = 1;
}
}
return ans;
}
