#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> segtree;
void build(int node, int l, int r) {
if (l == r) {
segtree[node] = 1;
return;
}
int mid = (l + r) / 2;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
segtree[node] = segtree[node*2] + segtree[node*2+1];
}
void update(int node, int l, int r, int pos, int val) {
if (l == r) {
segtree[node] = val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(node*2, l, mid, pos, val);
else update(node*2+1, mid+1, r, pos, val);
segtree[node] = segtree[node*2] + segtree[node*2+1];
}
int query(int node, int l, int r, int L, int R) {
if (R < l || L > r) return 0;
if (L <= l && r <= R) return segtree[node];
int mid = (l + r) / 2;
return query(node*2, l, mid, L, R) +
query(node*2+1, mid+1, r, L, R);
}
long long count_swaps(vector<int> s) {
int n = s.size();
N = n;
segtree.assign(4*n, 0);
long long ans = 0;
map<int, queue<int>> pos;
for (int i = 0; i < n; i++) {
pos[s[i]].push(i);
}
build(1, 0, n-1);
vector<int> used(n, 0);
for (int i = 0; i < n; i++) {
if (used[i]) continue;
int par = pos[-s[i]].front();
pos[-s[i]].pop();
pos[s[i]].pop();
if (i < par) {
ans += query(1, 0, n-1, i+1, par-1);
} else {
ans += query(1, 0, n-1, par+1, i-1);
}
used[i] = used[par] = 1;
update(1, 0, n-1, i, 0);
update(1, 0, n-1, par, 0);
}
return ans;
}
