#include "shoes.h"
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int n;
queue<int> shoes[100005][2];
int stn=1,tree[600005];
inline void push_down(int now){
tree[now<<1]+=tree[now];
tree[now<<1|1]+=tree[now];
tree[now]=0;
return;
}
inline void update(int now,int ls,int rs,int lq,int rq,int value){
if(rq<ls || rs<lq)return;
if(lq<=ls && rs<=rq){tree[now]+=value;return;}
push_down(now);
int mid=(ls+rs)>>1;
update(now<<1,ls,mid,lq,rq,value);
update(now<<1|1,mid+1,rs,lq,rq,value);
return;
}
inline int search(int now,int ls,int rs,int to){
//cout<<now<<" "<<ls<<" "<<rs<<" "<<to<<endl;
if(ls==to && rs==to)return tree[now];
push_down(now);
int mid=(ls+rs)>>1;
if(to<=mid)return search(now<<1,ls,mid,to);
else return search(now<<1|1,mid+1,rs,to);
}
inline int value(int now){return now<0?now*-1:now;}
inline long long int answer(int a,int b,bool way){
int ta=a+search(1,1,stn,a+1),tb=b+search(1,1,stn,b+1);//cout<<ta<<" "<<tb<<endl;
if(way)return tb-ta;else return tb-ta-1;
}
long long count_swaps(vector<int> s) {
n=s.size();while(stn<n)stn<<=1;
for(int i=0;i<n;i++)shoes[value(s[i])][s[i]<0].push(i);
long long int ans=0;int a=0,b;
for(int i=0;i<(n>>1);i++){
b=shoes[value(s[a])][s[a]>=0].front();//cout<<a<<" "<<b<<endl;
shoes[value(s[a])][0].pop();
shoes[value(s[a])][1].pop();
ans+=answer(a,b,s[a]>0);//cout<<ans<<endl;
update(1,1,stn,a+1,b+1,1);
if(a+1==b)a+=2;else a+=1;
}
return ans;
}
