#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
int n;
vector<int> t;
SegmentTree(int n) : n(n), t(4*n, 0) {}
void build(int node, int l, int r) {
if (l == r) {
t[node] = 1;
return;
}
int mid = (l + r) / 2;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
t[node] = t[node*2] + t[node*2+1];
}
void update(int node, int l, int r, int pos, int val) {
if (l == r) {
t[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);
t[node] = t[node*2] + t[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 t[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();
long long ans = 0;
map<int, queue<int>> pos;
for (int i = 0; i < n; i++) {
pos[s[i]].push(i);
}
SegmentTree seg(n);
seg.build(1, 0, n-1);
vector<int> used(n, 0);
for (int i = 0; i < n; i++) {
if (used[i]) continue;
int partner = pos[-s[i]].front();
pos[-s[i]].pop();
pos[s[i]].pop();
if (i < partner) {
ans += seg.query(1, 0, n-1, i+1, partner-1);
} else {
ans += seg.query(1, 0, n-1, partner+1, i-1);
}
used[i] = used[partner] = 1;
seg.update(1, 0, n-1, i, 0);
seg.update(1, 0, n-1, partner, 0);
}
return ans;
}
