#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
// #define F first
// #define S second
#include "shoes.h"
ll N;
vector<ll> tree;
void update(ll v, ll p, ll tl = 0, ll tr = N-1, ll i = 1) {
if (tl == tr) {tree[i] = v; return ;}
ll tm = (tl + tr) / 2;
if (p <= tm) update(v, p, tl, tm, i * 2);
else update(v, p, tm + 1, tr, i * 2 + 1);
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
ll query(ll l, ll r, ll tl = 0, ll tr = N-1, ll i = 1) {
if (l > r) return 0;
if (tl == l && tr == r) return tree[i];
ll tm = (tl + tr) / 2;
return query(l, min(r, tm), tl, tm, i * 2) + query(max(l, tm + 1), r, tm + 1, tr, i * 2 + 1);
}
ll count_swaps(vector<int> S) {
N = S.size();
tree.resize(4*N);
unordered_map<ll, queue<ll>> unpaired;
FOR(i, N) unpaired[S[i]].push(i);
vector<int> ok(N);
int res = 0;
// greedily pair shoes from the left
FOR(i, N) {
if (ok[i]) continue;
ll j = unpaired[-S[i]].front(); // move shoe at pos j leftward to pos i or i + 1
unpaired[-S[i]].pop();
unpaired[S[i]].pop();
res += j - i - 1 - query(i, j);
if (S[i] > 0) res++; // right shoe - need extra swap
update(1, j);
// val == 1: already moved to the left, dont double count swapping with it
ok[j] = 1;
}
return res;
}
// signed main() {
// cin.tie(0); ios::sync_with_stdio(false);
// }
