#include "shoes.h"
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
using namespace std;
struct Fenwick {
vector <int> aib;
int n;
inline void init(int _n) {
n = _n;
aib.resize(n + 1);
}
inline void update(int pos, int val) {
pos++;
for(int i = pos; i <= n; i += lsb(i)) {
aib[i] += val;
}
}
inline int query(int pos) {
pos++;
int ans = 0;
for(int i = pos; i > 0; i -= lsb(i)) {
ans += aib[i];
}
return ans;
}
inline int sum(int l, int r) {
return query(r) - query(l - 1);
}
};
long long count_swaps(std::vector<int> s) {
int n = s.size() / 2;
vector < vector <int> > l(n + 1), r(n + 1);
int i;
for(i = 0; i < 2 * n; i++) {
if(s[i] < 0) {
l[-s[i]].push_back(i);
}
else {
r[s[i]].push_back(i);
}
}
for(i = 1; i <= n; i++) {
sort(l[i].rbegin(), l[i].rend());
sort(r[i].rbegin(), r[i].rend());
}
Fenwick fen; fen.init(2 * n);
vector <bool> vis(2 * n);
ll ans = 0;
for(i = 0; i < 2 * n; i++) {
if(vis[i]) continue;
if(s[i] < 0) {
int pos = r[-s[i]].back();
vis[pos] = 1;
ans += pos - i - fen.sum(i + 1, pos - 1) - 1;
fen.update(pos, 1);
}
else {
int pos = l[s[i]].back();
vis[pos] = 1;
ans += pos - i - fen.sum(i + 1, pos - 1);
fen.update(pos, 1);
}
l[abs(s[i])].pop_back();
r[abs(s[i])].pop_back();
}
return ans;
}
