#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<ii>;
using vpl = vector<pl>;
#define mp make_pair
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()
ld dist(ld x, ld y, ld a, ld b) { return sqrt((x-a)*(x-a) + (y-b)*(y-b)); }
ll gcd(ll a , ll b){ return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b){ return (a * b) / gcd(a , b);}
ll fact(ll n) { return n > 1?(n * fact(n-1)):1;}
const ll MOD = 1000*1000*1000+7;
const long double EPS = 0.000000001;
const double PI = 3.14159265358979323846;
const long long INF = 1e18;
/// const int nx[4] = {0, 0, -1, 1}, ny[4] = {1, -1, 0, 0};
const int nx[8] = {2, 2, 1, -1, -2, -2, 1, -1};
const int ny[8] = {1, -1, 2, 2, -1, 1, -2, -2};
int st[4*200005];
void update(int v, int l, int r, int a, int b) {
if(l==r) { st[v]+=b; return; }
int mid=(l+r)/2;
if(a<=mid) update(v*2, l, mid, a, b);
else update(v*2+1, mid+1, r, a, b);
st[v]=st[v*2]+st[v*2+1];
}
int query(int v, int l, int r, int lo, int hi) {
if(l>hi||r<lo) return 0;
if(l>=lo&&r<=hi) return st[v];
return query(v*2, l, (l+r)/2, lo, hi)+query(v*2+1, (l+r)/2+1, r, lo, hi);
}
long long count_swaps(std::vector<int> s) {
ll n=s.size(); ll res=0;
priority_queue<pair<ii, int>>pq;
stack<int>lf[n], r[n];
for(int i=0;i<n;i++) {
update(1, 0, n-1, i, 1);
if(s[i]>0) lf[s[i]].push(i);
else r[-s[i]].push(i);
}
for(int l=1;l<=n/2;l++) {
if((int)lf[l].size()==0) continue;
ll a=lf[l].top(), b=r[l].top();
if(a>b) swap(a, b);
pq.push({{b, a}, l});
}
for(int l=n-1;l>=0;l--) {
if(l&1) {
ll j=pq.top().ss; ll u=lf[j].top(); lf[j].pop();
ll k=query(1, 0, n-1, 0, u);
res+=abs(l-k+1);
update(1, 0, n-1, u, -1);
}
else {
ll j=pq.top().ss; ll u=r[j].top(); r[j].pop();
ll k=query(1, 0, n-1, 0, u);
res+=abs(l-k+1);
update(1, 0, n-1, u, -1);
pq.pop();
if((int)lf[j].size()) {
ll a=lf[j].top(), b=r[j].top();
if(a>b) swap(a, b);
pq.push(mp(mp(b, a), j));
}
}
}
return res;
}
