#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long count_swaps(vector<int> s) {
int n = s.size() / 2;
vector<vector<int>> posL(n + 1), posR(n + 1);
for (int i = 0; i < n + n; i++) {
if (s[i] < 0) {
posL[-s[i]].push_back(i + 1);
} else {
posR[s[i]].push_back(i + 1);
}
}
for (int i = 1; i <= n; i++) {
sort(posL[i].begin(), posL[i].end(), greater<>());
sort(posR[i].begin(), posR[i].end(), greater<>());
}
vector<int> BIT(n + n + 1);
auto qry = [&] (int p) {
int ret = 0;
while (p) {
ret += BIT[p];
p -= p & -p;
}
return ret;
};
auto mod = [&] (int p, int x) {
while (p <= n + n) {
BIT[p] += x;
p += p & -p;
}
};
for (int i = 1; i <= n + n; i++) {
mod(i, 1);
}
long long ret = 0;
vector<bool> vis(n + n + 1);
for (int i = 1; i <= n + n; i++) {
if (!vis[i]) {
vis[i] = true;
if (s[i - 1] < 0) {
int pos = posR[-s[i - 1]].back();
mod(pos, -1), vis[pos] = true;
mod(i, -1), ret += qry(pos);
} else {
int pos = posL[s[i - 1]].back();
mod(pos, -1), vis[pos] = true;
ret += qry(pos), mod(i, -1);
}
posL[abs(s[i - 1])].pop_back();
posR[abs(s[i - 1])].pop_back();
}
}
return ret;
}
