#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
#define int long long
#define len(x) (int)(x.size())
#define inf 1000'000'000'000'000'000LL
#define all(x) x.begin(), x.end()
#define low_bit(x) (x & (-x))
template<typename T>
using vec = vector<T>;
template<typename T>
struct fenvik {
private:
vec<T> fen;
T _get(int x) {
T res = 0;
for (int i = x; i > 0; i -= low_bit(i)) {
res += fen[i];
}
return res;
}
void _add(int x, T val) {
for (int i = x; i < len(fen); i += low_bit(i)) {
fen[i] += val;
}
}
public:
void init(int x) {
fen.clear();
fen.resize(x + 1);
}
void inc(int i, T x) {
i++;
_add(i, x);
}
T get(int l, int r) {
if (l > r) return 0;
if (l == 0) return _get(r + 1);
return _get(r + 1) - _get(l);
}
T get(int i) {
return get(i, i);
}
void set(int i, T x) {
inc(i, x - get(i));
}
};
int count_swaps(vec<i32> s) {
int n = len(s);
map<int, deque<int>> pos;
set<int> unpaired;
for (int i = 0; i < len(s); i++) {
pos[s[i]].push_back(i);
unpaired.insert(i);
}
int ans = 0;
vec<int> pair(n, -1);
for (int i = 0; i < n; i++) {
if (!unpaired.count(i)) continue;
if (s[i] > 0) ans++;
int ps = pos[-s[i]].front();
pos[-s[i]].pop_front();
pos[s[i]].pop_front();
s[i] = abs(s[i]);
s[ps] = abs(s[ps]);
pair[i] = ps;
pair[ps] = i;
unpaired.erase(i);
unpaired.erase(ps);
}
fenvik<int> exist;
exist.init(n);
for (int i = 0; i < n; i++) {
exist.set(i, 1);
}
for (int i = 0; i < n; i++) {
if (exist.get(i) == 0) continue;
exist.set(pair[i], 0);
ans += exist.get(i + 1, pair[i]);
}
return ans;
}
