#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct segtree {
vector<int> tree;
int n;
segtree(int n) : n(n) {
tree.resize(2*n);
}
void upd(int u, int k) {
tree[u += n] += k;
for (u /= 2; u >= 1; u /= 2) {
tree[u] = tree[2*u] + tree[2*u+1];
}
}
int qry(int l, int r) {
int res = 0;
l += n; r += n;
while (l <= r) {
if (l % 2 == 1) res += tree[l++];
if (r % 2 == 0) res += tree[r--];
l /= 2;
r /= 2;
}
return res;
}
};
long long count_swaps(std::vector<int> s) {
int n = s.size()/2;
vector<int> v = s;
vector<int> goal;
map<int, int> cnt;
for (int i = 0; i < 2*n; i++) {
int x = v[i];
if (cnt[x] > 0) cnt[x]--;
else {
goal.emplace_back(-abs(x));
goal.emplace_back(abs(x));
cnt[-x]++;
}
}
map<int, vector<int>> vec;
for (int i = 2*n-1; i >= 0; i--) {
vec[goal[i]].emplace_back(i);
}
long long ans = 0;
segtree st(2*n+1);
for (int i = 0; i < 2*n; i++) {
int j = vec[v[i]].back();
vec[v[i]].pop_back();
ans += st.qry(j, 2*n);
st.upd(j, 1);
}
return ans;
}
