#include <bits/stdc++.h>
using namespace std;
struct BIT {
int n;
vector<int> t;
BIT(int _n):n(_n),t(n+1,0){}
void add(int i,int v){ for(;i<=n;i+=i&-i) t[i]+=v; }
int sum(int i){ int r=0; for(;i>0;i-=i&-i) r+=t[i]; return r;}
};
long long count_swaps(vector<int> S) {
// vector of occurences for each type
int N = S.size();
vector<pair<int, int> > occ[N / 2 + 1];
for (int i = 0; i < N; i++) {
occ[abs(S[i])].push_back({S[i], i});
}
long long ans = 0;
vector<pair<int, int> > intervals;
for (int x = 1; x <= N / 2; x++) {
vector<pair<int, int> > &v = occ[x];
int m = v.size() / 2;
sort(v.begin(), v.end());
for (int i = 0; i < m; i++) {
int l = v[i].second;
int r = v[i + m].second;
if (l > r) {
swap(l, r);
ans++;
}
intervals.push_back({l + 1, r + 1});
}
}
sort(intervals.begin(), intervals.end());
BIT bit(N);
for (int i = 1; i <= N; i++)
bit.add(i, 1);
for (int i = 1; i <= N; i++) {
int l = intervals[i].first;
int r = intervals[i].second;
bit.add(i, 1);
ans += bit.sum(r - 1) - bit.sum(l);
bit.add(l, -1);
bit.add(r, -1);
}
return ans;
}
