#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<std::pair<int, bool>>> map;
for (int i = 0; i < n; ++i) {
if (s[i] > 0) {
map[s[i]].emplace_back(i, true);
} else {
map[-s[i]].emplace_back(i, false);
}
}
ll ret = 0;
Fenwick fen(n + 1);
Vec<std::pair<int, int>> pair;
for (const auto& [x, vec] : map) {
const int m = (int) vec.size();
int pos = 0, neg = 0;
Vec<int> assign(m);
for (int i = 0; i < m; ++i) {
const auto [j, f] = vec[i];
if (f) {
assign[2 * pos + 1] = i;
pos += 1;
} else {
assign[2 * neg] = i;
neg += 1;
}
}
for (int i = 0; i < m / 2; ++i) {
const int l = 2 * i;
const int r = 2 * i + 1;
if (vec[assign[l]].first > vec[assign[r]].first) {
ret += 1;
std::swap(assign[l], assign[r]);
}
pair.emplace_back(vec[assign[l]].first, vec[assign[r]].first);
}
}
std::sort(pair.begin(), pair.end());
for (const auto [l, r]: pair) {
ret += fen.fold(0, l + 1);
ret += fen.fold(0, r + 1);
fen.add(l + 1, 1);
fen.add(r, -1);
}
return ret;
}
