#include <bits/stdc++.h>
using namespace std;
#include "shoes.h"
const int MAXN=2e5+5;
int seg[MAXN*4],offset=1;
void update(int idx,int val){
idx+=offset;
seg[idx]=val;
idx/=2;
while(idx>0){
seg[idx]=seg[idx*2]+seg[idx*2+1];
idx/=2;
}
}
int query(int node,int qlo,int qhi,int lo,int hi){
if(qlo>qhi)return 0;
if(lo>=qlo && hi<=qhi)return seg[node];
if(lo>qhi || hi<qlo)return 0;
int mid=(lo+hi)/2;
return query(node*2,qlo,qhi,lo,mid)+query(node*2+1,qlo,qhi,mid+1,hi);
}
/*
2
1 -2 -1 2
*/
long long count_swaps(std::vector<int> s) {
const int N=s.size();
while(offset<N)offset*=2;
queue<int> qr[N],ql[N];
for(int i=0;i<N;i++){
if(s[i]>0)qr[s[i]].push(i);
else ql[abs(s[i])].push(i);
update(i,1);
}
long long ans=0;
for(int i=0;i<N;i++){
if(s[i]<0){
int idx=qr[abs(s[i])].front();
ans+=query(1,0,i-1,0,offset-1);
update(i,0);
ans+=query(1,0,idx-1,0,offset-1);
update(idx,0);
}
else{
int idx=ql[abs(s[i])].front();
ans+=query(1,0,i-1,0,offset-1);
ans+=query(1,0,idx-1,0,offset-1);
update(i,0);
update(idx,0);
}
qr[abs(s[i])].pop();
ql[abs(s[i])].pop();
}
return ans;
}
