#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
long long count_swaps(std::vector<int> s) {
#define int long long
int n = (int)s.size();
vector<vector<int>> pos(n + 1), neg(n + 1);
for (int i = n - 1; i >= 0; i--) {
if (s[i] < 0) {
neg[-s[i]].pb(i);
}
else {
pos[s[i]].pb(i);
}
}
vector<int> fen(2 * n);
auto update = [&](int i, int v) {
for (++i ; i < 2 * n; i += i & -i) {
fen[i] += v;
}
};
auto sum = [&](int i) {
int ret = 0;
for (++i ; i; i -= i & -i) {
ret += fen[i];
}
return ret;
};
auto get = [&](int l, int r) {
if (l == 0) {
return sum(r);
}
else {
return sum(r) - sum(l - 1);
}
};
for (int i = 0; i < n; i++) {
update(i, 1);
}
long long ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] < 0) {
if (neg[-s[i]].empty() || neg[-s[i]].back() != i) {
continue;
}
int j = pos[-s[i]].back();
pos[-s[i]].pop_back();
neg[-s[i]].pop_back();
ans += get(i, j) - 2;
update(i, -1);
update(j, -1);
}
else {
if (pos[s[i]].empty() || pos[s[i]].back() != i) {
continue;
}
int j = neg[s[i]].back();
neg[s[i]].pop_back();
pos[s[i]].pop_back();
ans += get(i, j) - 2 + 1;
update(i, -1);
update(j, -1);
}
}
return ans;
}
