#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAX = 1e5;
vector<int> fenwick(MAX + 10);
void update(int n) {
for (; n <= MAX; n += n & -n) fenwick[n]++;
}
int query(int n) {
int S = 0;
for (; n > 0; n -= n & -n) S += fenwick[n];
return S;
}
int count_swaps(vector<signed> S) {
const int N = S.size();
map<int, int> cnt;
map<int, vector<pair<int, int> > > pos;
vector<int> A(N);
for (int i = 0; i < N; i++) pos[abs(S[i]) + N * cnt[S[i]]++].emplace_back(i, S[i] > 0);
int n = 0, c, d, ans = 0;
for (auto kv: pos) {
c = 0, d = 0;
const int M = kv.second.size();
for (int i = 0; i < M; i++) {
if (kv.second[0].second == kv.second[i].second) {
A[kv.second[i].first] = n + ((c++) << 1);
} else {
A[kv.second[i].first] = n + ((d++) << 1) + 1;
}
}
n += M;
if (kv.second[0].second) ans += (M >> 1);
}
for (int i = 0; i < N; i++) {
ans += query(N - A[i]);
update(N - A[i]);
}
return ans;
}
