#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct SegTree {
int sz;
vector<int> tree;
int ql, qr;
void merge(int i) {
tree[i] = tree[2*i]+tree[2*i+1];
}
SegTree(int N) {
sz = 1;
while (sz < N) sz *= 2;
tree.resize(2*sz);
for (int i = sz; i < sz+N; i++) tree[i] = 1;
for (int i = sz+N; i < 2*sz; i++) tree[i] = 0;
for (int i = sz-1; i >= 1; i--) merge(i);
}
int __query(int ni, int nl, int nr) {
if (qr <= nl || nr <= ql) return 0;
if (ql <= nl && nr <= qr) return tree[ni];
int nm = (nl+nr)/2;
return __query(2*ni, nl, nm) + __query(2*ni+1, nm, nr);
}
int query(int l, int r) {
ql = l;
qr = r;
return __query(1, 0, sz);
}
void set0(int i) {
i += sz;
tree[i] = 0;
for (i /= 2; i >= 1; i /= 2) {
merge(i);
}
}
};
long long count_swaps(vector<int> S) {
const int N = S.size() / 2;
vector<queue<int>> queues(N+1); // Index where given numbers appear
vector<int> other(2*N); // Index of other pair element
for (int i = 0; i < 2*N; i++) {
const int x = abs(S[i]);
if (!queues[x].size() || S[queues[x].front()] == S[i]) {
queues[x].push(i);
} else {
const int j = queues[x].front();
queues[x].pop();
other[i] = j;
other[j] = i;
}
}
SegTree seg(2*N);
long long ans = 0;
for (int i = 0; i < 2*N; i++) {
if (other[i] < i) continue;
if (S[i] > 0) ans++; // this is a right shoe, to be swapped at the end
ans += seg.query(i+1, other[i]);
seg.set0(i);
seg.set0(other[i]);
}
return ans;
}
