#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
int tree[100010];
queue<int> q1[100010];
queue<int> q2[100010];
int visited[100010];
int read(int idx)
{
int sum=0;
while(idx>0)
{
sum+=tree[idx];
idx-=(idx&-idx);
}
return sum;
}
void update(int idx,int val,int n)
{
while(idx<=n)
{
tree[idx]+=val;
idx+=(idx&-idx);
}
}
long long count_swaps(std::vector<int> s) {
int n=s.size();
long long sum=0;
for(int i=1;i<=n;i++) update(i,1,n);
for(int i=1;i<=n;i++)
{
if(s[i-1]>0) q1[s[i-1]].push(i);
else q2[-s[i-1]].push(i);
}
for(int i=1;i<=n;i++)
{
if(visited[i]) continue;
update(i,-1,n);
visited[i]++;
if(s[i-1]<0)
{
int x=-s[i-1];
int idx=q1[x].front();
q1[x].pop();
q2[x].pop();
while(visited[idx])
{
q1[x].pop();
idx=q1[x].front();
}
sum+=read(idx)-1;
if(idx<i) sum++;
update(idx,-1,n);
visited[idx]++;
//printf("idx=%d sum=%d i=%d\n",idx,sum,i);
}
else
{
int x=s[i-1];
int idx=q2[x].front();
q2[x].pop();
q1[x].pop();
while(visited[idx])
{
q2[x].pop();
idx=q2[x].front();
}
sum+=read(idx)-1;
if(idx>i) sum++;
update(idx,-1,n);
//update(i,-1,n);
visited[idx]++;
//printf("idx=%d sum=%d i=%d\n",idx,sum,i);
}
// for(int i=1;i<=n;i++)
// {
// printf("%d ",read(i)-read(i-1));
// }
// printf("\n");
}
return sum;
}
