#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int seg[600000];
int n,N,L,R;
int slv(int l=1,int r=N,int in=1){
if(l>R||r<L)return 0;
if(l>=L&&r<=R)return seg[in];
int mid=(l+r)/2;
return slv(l,mid,in*2)+slv(mid+1,r,in*2+1);
}
void upd(int in){
in=in+N;
seg[in]=0;
in/=2;
while(in){
seg[in]=seg[in*2]+seg[in*2+1];
in/=2;
}
}
long long count_swaps(vector<int> s){
n=s.size();
N=exp2(ceil(log2(n)));
long long ans=0;
deque<int>dq[2][n+1];
for(int i=0;i<n;i++)dq[s[i]>0][abs(s[i])].push_back(i);
for(int i=0;i<N;i++)seg[i+N]=1;
for(int i=N-1;i;i--)seg[i]=seg[i*2]+seg[i*2+1];
L=1;
for(int i=0;i<n/2;i++){
int l=0,r=n-1,mid,f=0;
while(l<=r){
mid=(l+r)/2;
R=mid+1;
if(slv()==0)l=mid+1;
else{r=mid-1;f=mid;}
}
int k=abs(s[f]);
R=dq[0][k][0];
dq[0][k].pop_front();
if(R>=1)ans+=slv();
upd(R);
R=dq[1][k][0];
dq[1][k].pop_front();
if(R>=1)ans+=slv();
upd(R);
}
return ans;
}
