#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
struct BIT {
int n; vector<int> f;
BIT(int n=0): n(n), f(n+1,0) {}
void add(int i,int v){ for(; i<=n; i+=i&-i) f[i]+=v; }
int sum(int i){ int s=0; for(; i>0; i-=i&-i) s+=f[i]; return s; }
};
int64 count_swaps(vector<int> S){
const int N = (int)S.size();
// group by absolute size: store (value, index)
unordered_map<int, vector<pair<int,int>>> by;
by.reserve(N*2);
for (int i=0;i<N;i++) by[abs(S[i])].push_back({S[i], i});
// build pairs (l, r) with l<r; add +1 to answer when right shoe is left of left shoe
vector<pair<int,int>> pairs; pairs.reserve(N/2);
int64 ans = 0;
for (auto &kv : by){
auto &v = kv.second;
// sort by value: all negatives (-x = left shoes) come before positives (+x = right shoes)
sort(v.begin(), v.end()); // (-x, idx)...(+x, idx) for this size
int k = (int)v.size()/2;
for (int j=0;j<k;j++){
int l = v[j].second; // j-th left
int r = v[j+k].second; // j-th right
if (l > r){ swap(l, r); ++ans; } // extra 1 if right appears before left
pairs.emplace_back(l+1, r+1); // BIT is 1-based
}
}
// process pairs left->right, summing remaining elements between l and r
sort(pairs.begin(), pairs.end());
BIT bit(N);
for (int i=1;i<=N;i++) bit.add(i, 1); // everyone present
for (auto &pr : pairs){
int l = pr.first, r = pr.second;
ans += bit.sum(r-1) - bit.sum(l); // strictly between l and r
bit.add(l, -1); bit.add(r, -1); // remove endpoints
}
return ans;
}
