#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
int used[1000005],n,p[1000005];
queue<int>v[1000005];
void update(int l,int r,int q,int h)
{
if(l>q||r<q)return;
if(l==r)
{
p[h]--;
return;
}
int mid=(l+r)/2;
update(l,mid,q,h*2);
update(mid+1,r,q,h*2+1);
p[h]=p[h*2]+p[h*2+1];
}
int query(int l,int r,int ql,int qr,int h)
{
if(l>qr||r<ql)return 0;
if(l>=ql&&r<=qr)return p[h];
int mid=(l+r)/2;
return query(l,mid,ql,qr,h*2)+query(mid+1,r,ql,qr,h*2+1);
}
long long int count_swaps(vector<int> s)
{
n=s.size();
long long int br=0;
for(int i=0;i<n;i++)
{
if(s[i]>0)v[s[i]].push(i);
else v[s[i]*-1+n+1].push(i);
}
int ind;
for(int i=0;i<n;i++)
{
if(used[i])continue;
if(s[i]<0)
{
ind=v[s[i]*-1].front();
v[s[i]*-1+n+1].pop();
v[s[i]*-1].pop();
}
else
{
ind=v[s[i]+n+1].front();
v[s[i]].pop();
v[s[i]+n+1].pop();
}
used[ind]=1;
update(1,n,ind+1,1);
ind+=query(1,n,i+1,ind,1);
if(s[i]<0)ind--;
br+=(ind-i);
}
return br;
}
