#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
struct Fenwick {
int n;
vector<int> tree;
Fenwick(int n_) : n(n_), tree(n + 1) {}
inline int lsb(int x) {
return x & -x;
}
void Update(int pos, int val) {
for (++pos; pos <= n; pos += lsb(pos))
tree[pos] += val;
}
int Query(int pos) {
int ret = 0;
for (++pos; pos >= 1; pos -= lsb(pos))
ret += tree[pos];
return ret;
}
};
long long count_swaps(vector<int> s) {
int n = s.size();
vector<vector<int>> left(n + 1), right(n + 1);
for (int i = 0; i < n; ++i) {
if (s[i] < 0) left[-s[i]].emplace_back(i);
else right[s[i]].emplace_back(i);
}
vector<pair<int, int>> pairs; pairs.reserve(n);
for (int size = 1; size <= n / 2; ++size) {
assert(left[size].size() == right[size].size());
for (int j = 0; j < (int)left[size].size(); ++j) {
pairs.emplace_back(left[size][j], right[size][j]);
}
}
sort(pairs.begin(), pairs.end(), [](const pair<int, int> &a, const pair<int, int> &b){
return a.first + a.second < b.first + b.second;
});
Fenwick tree(n);
long long idx = 0, ans = 0LL;
for (auto &p : pairs) {
int l, r; tie(l, r) = p;
l += tree.Query(l);
r += tree.Query(r);
//~ cerr << l << ' ' << r << endl;
ans += l - idx + r - idx - 1;
if (l > r) ++ans;
tree.Update(0, 2);
tree.Update(p.first, -1);
tree.Update(p.second, -1);
idx += 2;
}
return ans;
}
