#include <bits/stdc++.h>
#include "shoes.h"
struct node {
int min, max;
node *left, *right;
int value;
node(int l, int r) {
min = l;
max = r;
if (r == l + 1) {
left = right = nullptr;
} else {
left = new node(l, (l + r) / 2);
right = new node((l + r) / 2, r);
}
value = max - min;
}
void erase(int x) {
if (x < min || x >= max) return;
value--;
if (x == min && x + 1 == max) return;
left->erase(x);
right->erase(x);
}
int query(int l, int r) const {
l = std::max(l, min);
r = std::min(r, max);
if (l >= r) return 0;
if (l >= max || r <= min) return 0;
if (l == min && r == max) return value;
return left->query(l, r) + right->query(l, r);
}
};
long long count_swaps(std::vector<int> s) {
int N = s.size() / 2;
node tree(0, 2 * N);
long long ans = 0;
auto moveLeft = [&](int idx) {
ans += tree.query(0, idx);
tree.erase(idx);
};
std::map<int, std::queue<int>> rights;
for (int i = 0; i < 2 * N; ++i) {
if (s[i] > 0) {
rights[s[i]].push(i);
}
}
for (int i = 0; i < 2 * N; ++i) {
if (s[i] < 0) {
moveLeft(i);
int x = rights[-s[i]].front();
rights[-s[i]].pop();
moveLeft(x);
}
}
return ans;
}
