#include "shoes.h"
#include <bits/stdc++.h>
#ifdef DEBUG
#define debug(...) println(clog, __VA_ARGS__)
#else
#define debug(...)
#endif
#define forall(i, s, e) for(int i=(s); i<(e); i++)
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using aii = array<int, 2>;
using all = array<ll, 2>;
const ll IDENTITY = 0;
struct segment {
int N;
vector<ll> T;
segment() {};
segment(int n){
N = n;
T.assign(2*N, IDENTITY);
}
void upd(int i, ll x){
i += N;
T[i] = x;
for(; i>1; i/=2)
T[i/2] = T[i] + T[i^1];
}
ll query(int l, int r){ // [l, r)
ll res = 0;
l += N, r += N;
for (; l < r; l/=2, r/=2) {
if(l%2) res += T[l++];
if(r%2) res += T[--r];
}
return res;
}
ll query(int i){
return T[i+N];
}
};
ll count_swaps(vi s) {
int N = s.size();
map<int, vi> Mp;
set<int> S;
forall(i, 0, N) {
S.insert(abs(s[i]));
Mp[s[i]].push_back(i);
}
vector<aii> rng;
ll ans = 0;
for(int i:S) {
vi &pos = Mp[i];
vi &neg = Mp[-i];
assert(pos.size() == neg.size());
forall(j, 0, sz(pos)) {
ans += abs(pos[j]-neg[j]) - 1 + (pos[j]<neg[j]);
int l=pos[j], r=neg[j];
if(l>r) swap(l,r);
rng.push_back({l,r});
}
}
sort(rng.begin(), rng.end());
segment ST(N);
for(auto [l,r]:rng) {
ans -= ST.query(l, r+1);
ST.upd(r, 1);
}
return ans;
}
