#pragma GCC optimization ("O3")
#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long int ll;
const ll MAX_N = ll(1e5 + 3);
ll st[4 * MAX_N];
void build(ll p, ll tl, ll tr) {
if (tl == tr) {
st[p] = 0;
return;
}
ll m = (tl + tr) / 2;
build(2*p, tl, m);
build(2*p+1, m+1, tr);
st[p] = st[2*p] + st[2*p+1];
}
ll query(ll p, ll tl, ll tr, ll l, ll r) {
if (l > r) return 0;
if (tl == l && tr == r) {
return st[p];
}
ll m = (tl + tr) / 2;
ll L = query(2*p, tl, m, l, min(r, m));
ll R = query(2*p+1, m+1, tr, max(l, m+1), r);
return L + R;
}
void update(ll p, ll tl, ll tr, ll k, ll v) {
if (tl == tr) {
st[p] = v;
return;
}
ll m = (tl + tr) / 2;
if (k <= m) {
update(2*p, tl, m, k, v);
} else {
update(2*p+1, m+1, tr, k, v);
}
st[p] = st[2*p] + st[2*p+1];
}
ll count_swaps(vector<int> s) {
ll n = s.size();
vector<ll> taken(n);
vector<queue<ll>> neg(n + 1);
vector<queue<ll>> pos(n + 1);
vector<ll> pairs(n);
// make pairs
for (ll i = 0; i < n; i++) {
if (s[i] < 0) {
if (!pos[-s[i]].empty()) {
pairs[pos[-s[i]].front()] = i;
pos[-s[i]].pop();
} else {
neg[-s[i]].push(i);
}
} else {
if (!neg[s[i]].empty()) {
pairs[neg[s[i]].front()] = i;
neg[s[i]].pop();
} else {
pos[s[i]].push(i);
}
}
}
build(1, 0, n-1);
ll ans = 0;
for (ll i = 0; i < n; i++) {
if (taken[i]) continue;
ll j = pairs[i];
ans += j - i - query(1, 0, n-1, i, j);
if (s[i] < 0) ans--;
taken[i] = true;
taken[j] = true;
update(1, 0, n-1, i, taken[i]);
update(1, 0, n-1, j, taken[j]);
}
return ans;
}
// queue for each shoe size
// use queue to find best pairs
// use something like a segtree to find number of swaps for each pair
