#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
struct Segment {
int n;
vector<int> t;
Segment(int n, vector<int> v) : n(n) {
t.resize(2 * n);
for (int i = 0; i < n; ++i) {
t[i + n] = v[i];
}
for (int i = n-1; i > 0; --i) {
t[i] = t[2*i] + t[2*i+1];
}
}
void upd(int i, int v) {
for (t[i += n] = v; i > 1; i >>= 1) {
t[i >> 1] = t[i] + t[i ^ 1];
}
}
int sum(int l, int r) {
int ans = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans += t[l++];
if (r & 1) ans += t[--r];
}
return ans;
}
};
LL count_swaps(vector<int> s) {
int n = s.size();
map<int, array<vector<int>, 2>> mp;
for (int i = 0; i < n; ++i) {
mp[abs(s[i])][s[i] > 0].push_back(i);
}
vector<int> p(n);
for (auto& [_, pairs] : mp) {
assert(pairs[0].size() == pairs[1].size());
for (int i = 0; i < (int)pairs[0].size(); ++i) {
p[pairs[0][i]] = pairs[1][i];
p[pairs[1][i]] = pairs[0][i];
}
}
Segment st(n, vector<int>(n, 1));
LL ans = 0;
for (int i = 0; i < n; ++i) {
if (p[i] < i) continue;
ans += (s[i] > 0);
st.upd(i, 0);
st.upd(p[i], 0);
ans += st.sum(i, p[i]);
}
return ans;
}
