#include "shoes.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long N=200010;
typedef pair<long long,long long> ii;
typedef pair<double,double> dd;
long long n,c[N],temp[N],pr[N],cnt;
queue<int> nxt[100001][2];
long long merge(int l,int mid,int r)
{
long long cnt=0;
int i=l,j=mid,k=l;
while((i<=mid-1)&&(j<=r))
{
if(c[i]<=c[j]) temp[k++]=c[i++];
else
{
temp[k++]=c[j++];
cnt+=1ll*(mid-i);
}
}
while(i<=mid-1) temp[k++]=c[i++];
while(j<=r) temp[k++]=c[j++];
for(int i=l;i<=r;i++) c[i]=temp[i];
return cnt;
}
long long mergesort(int l,int r)
{
int cnt=0;
if(l<r)
{
long long mid=(l+r)/2;
cnt+=mergesort(l,mid);
cnt+=mergesort(mid+1,r);
cnt+=merge(l,mid+1,r);
}
return cnt;
}
long long count_swaps(std::vector<int> s) {
n=s.size()/2;
for(int i=2*n-1;i>=0;i--)
{
if(s[i]<0)
{
if(nxt[-s[i]][1].empty()) nxt[-s[i]][0].push(i);
else
{
pr[i]=nxt[-s[i]][1].front();
nxt[-s[i]][1].pop();
}
}
else
{
if(nxt[s[i]][0].empty()) nxt[s[i]][1].push(i);
else
{
pr[i]=nxt[s[i]][0].front();
nxt[s[i]][0].pop();
}
}
}
for(int i=0;i<2*n;i++)
{
if(pr[i]!=0)
{
c[i]=++cnt;
c[pr[i]]=++cnt;
if(s[i]>0) swap(c[i],c[pr[i]]);
}
}
return mergesort(0,2*n-1);
}
