#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int seg_tree[850000];
int n;
int N;
void update(int h, int l=0, int r=N-1, int node=1)
{
seg_tree[node]++;
if(l==r)
{
return;
}
int m=(l+r)/2;
if(h<=m)
{
update(h,l,m,node*2);
}
else
{
update(h,m+1,r,node*2+1);
}
}
long long query(int hl, int hr, int l=0, int r=N-1, int node=1)
{
if(hl<=l && r<=hr)
{
return seg_tree[node];
}
int m=(l+r)/2;
int res=0;
if(hl<=m)
{
res+=query(hl,hr,l,m,node*2);
}
if(m+1<=hr)
{
res+=query(hl,hr,m+1,r,node*2+1);
}
return res;
}
long long count_swaps(std::vector <int> s)
{
n=s.size()/2;
N=2*n;
vector <queue <int> > q(n+1);
int k=1;
vector <int> nw(2*n);
for(int i=0;i<s.size();i++)
{
if(q[abs(s[i])].size())
{
if(q[abs(s[i])].front() < 0 && s[i]>0)
{
nw[(-q[abs(s[i])].front())-1]=-k;
nw[i]=k;
k++;
q[abs(s[i])].pop();
}
else if(q[abs(s[i])].front() > 0 && s[i]<0)
{
nw[(q[abs(s[i])].front())-1]=k;
nw[i]=-k;
k++;
q[abs(s[i])].pop();
}
else if(s[i]>0)
{
q[abs(s[i])].push(i+1);
}
else
{
q[abs(s[i])].push(-i-1);
}
}
else if(s[i]>0)
{
q[abs(s[i])].push(i+1);
}
else
{
q[abs(s[i])].push(-i-1);
}
}
vector <int> t(n+1,-1);
vector <long long> p(2*n);
k=0;
for(int i=0;i<nw.size();i++)
{
if(t[abs(nw[i])]==-1)
{
t[abs(nw[i])]=k;
k++;
}
p[i]=2*t[abs(nw[i])];
if(nw[i]>0)
{
p[i]++;
}
}
/*for(int i=0;i<nw.size();i++)
{
printf("%d ",nw[i]);
}
printf("\n");
for(int i=0;i<p.size();i++)
{
printf("%lld ",p[i]);
}
printf("\n");*/
vector <long long> p_inv (2*n);
for(int i=0;i<p.size();i++)
{
p_inv[p[i]]=i;
}
/*for(int i=0;i<p_inv.size();i++)
{
printf("%lld ",p_inv[i]);
}
printf("\n");*/
long long ans=0;
for(long long i=0;i<p_inv.size();i++)
{
ans+=p_inv[i];
ans-=query(0,p_inv[i]);
update(p_inv[i]);
}
return ans;
}
