#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
struct Fenwick { // 0-indexed
vll tree;
ll n;
Fenwick (ll n): tree(n, 0), n(n) {}
ll query (ll ql, ll qr) { return query(qr) - query(ql-1); }
ll query (ll at) { // 0-indexed
ll ans = 0;
for (; at >= 0; at &= at+1, at--) ans += tree[at];
return ans;
}
void update (ll at, ll val) { // 0-indexed
for (; at < n; at |= at+1) tree[at] += val;
}
};
ll count_swaps (vector <int> vei) {
vll ve(vei.size());
ll n = ve.size()/2;
for (ll i = 0; i < 2*n; i++) ve[i] = vei[i];
Fenwick ft(2*n); // ft[i] means that there are now ft[i] shoes in position i
ll ans = 0;
for (ll i = 0; i < 2*n; i++) {
ft.update(i, 1);
}
vll next(2*n, -15);
{vector <queue <ll> > nextqs(n+1);
for (ll i = 2*n-1; i >= 0; i--) {
queue <ll> &q = nextqs[abs(ve[i])];
if (!q.size() || ve[q.front()] == ve[i]) { // not complement
q.push(i);
} else { // complements
next[i] = q.front();
q.pop();
}
}}
for (ll i = 0; i < 2*n; i++) {
ll j = next[i];
if (j < 0) continue;
ans += ft.query(i+1, j-1) + (ve[i] > 0); // extra flip
ft.update(j, -1); // makes it 0
ft.update(i, 1); // irrelevant but, still, two shoes are now here
}
return ans;
}
