#include "shoes.h"
#include <bits/stdc++.h>
struct SegmentTree {
int n;
std::vector<int> t;
SegmentTree(int _n) : n(_n), t(2 * n) {}
void update(int l, int r, int v) {
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) t[l] += v, l++;
if (r & 1) --r, t[r] += v;
}
}
int query(int p) {
int ans = 0;
for (p += n; p > 0; p >>= 1) {
ans += t[p];
}
return ans;
}
};
long long count_swaps(std::vector<int> s) {
int n = (int) s.size() / 2;
SegmentTree tree(2 * n);
for (int i = 0; i < 2 * n; i++) {
tree.update(i, i + 1, i);
}
std::map<int, std::vector<int>> mp;
std::set<std::pair<int, int>> st;
for (int i = 2 * n; i >= 0; i--) {
mp[s[i]].push_back(i);
st.insert({i, s[i]});
}
long long ans = 0;
for (int i = 0; i < n; i++) {
int f = 2 * i;
int v = st.begin()->second;
auto pos = mp[-v].back();
mp[-v].pop_back();
mp[v].pop_back();
int real_pos = tree.query(pos);
ans += real_pos - (f + (v < 0));
tree.update(0, pos, 1);
st.erase(st.begin());
st.erase({pos, s[pos]});
}
return ans;
}
