#include <bits/stdc++.h>
using namespace std;
vector<int> tree;
int leng=0;
void update(int v,int currStart,int currEnd,int lookStart,int lookEnd){
if (currStart>=lookStart && currEnd<=lookEnd){
tree[v]++;
return;
}
if (currStart>lookEnd || currEnd<lookStart) return;
int mid=(currStart+currEnd)/2;
update(2*v,currStart,mid,lookStart,lookEnd);
update(2*v+1,mid+1,currEnd,lookStart,lookEnd);
}
int get(int pos){
pos+=leng;
int ans=tree[pos];
while (pos>1){
pos/=2;
ans+=tree[pos];
}
return ans;
}
int64_t count_swaps(vector<int> S){
tree.clear();
int n=S.size();
for (int i=1;i<=21;i++){
int p=(1<<i);
if (p>=n){
leng=p;
break;
}
}
tree.resize(2*leng);
vector<bool> skip(n);
iota(tree.begin()+leng+1,tree.end(),1);
vector<pair<priority_queue<int,vector<int>,greater<>>,priority_queue<int,vector<int>,greater<>>>> pqs(n+1);
for (int i=0;i<n;i++){
if (S[i]>0){
pqs[S[i]].first.push(i);
} else {
pqs[S[i]*-1].second.push(i);
}
}
int64_t swaps=0;
for (int i=0;i<n;i++){
if (skip[i]) continue;
int now=get(i);
int next;
if (S[i]>0){
//szukam w ujemnych na .second
next=pqs[S[i]].second.top();
pqs[S[i]].second.pop();
pqs[S[i]].first.pop(); //usuwamy now
} else {
//szukam w dodatnich na .first
next=pqs[S[i]*-1].first.top();
pqs[S[i]*-1].first.pop();
pqs[S[i]*-1].second.pop();//usuwamy now
}
update(1,0,leng-1,0,next-1);
skip[i]=true;
skip[next]=true;
next=get(next);
swaps+=next-now-1;
if (S[i]>0) swaps++;
}
return swaps;
}
