#include <bits/stdc++.h>
#include "shoes.h"
using ll = long long;
template <class T> using Vec = std::vector<T>;
struct Fenwick {
Vec<int> data;
Fenwick(const int n): data(n + 1) {}
void add(int i, const int x) {
for (i += 1; i < (int) data.size(); i += i & -i) {
data[i] += x;
}
}
int get(int i) const {
int x = 0;
for (; i > 0; i -= i & -i) {
x += data[i];
}
return x;
}
int fold(const int l, const int r) const {
return get(r) - get(l);
}
};
ll count_swaps(Vec<int> s) {
const int n = (int) s.size();
std::map<int, Vec<int>> map;
for (int i = n - 1; i >= 0; --i) {
map[s[i]].push_back(i);
}
Vec<char> done(n);
Vec<int> p(n);
int idx = 0;
for (int i = 0; i < n; ++i) {
if (done[i]) continue;
map[s[i]].pop_back();
const auto j = map[-s[i]].back();
map[-s[i]].pop_back();
done[i] = done[j] = true;
if (s[i] > 0) {
p[idx++] = j;
p[idx++] = i;
} else {
p[idx++] = i;
p[idx++] = j;
}
}
ll ret = 0;
Fenwick fen(n);
for (const auto i: p) {
ret += fen.fold(i, n);
fen.add(i, 1);
}
return ret;
}
