#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PB push_back
struct segtree{
long long dd, htt, mid, val;
segtree *L, *R;
segtree(int l, int r){
//cout<<l<<" "<<r<<endl;
htt=r;
dd=l;
val=0;
mid=(htt+dd)/2;
if(l!=r){
L=new segtree(l, mid);
R=new segtree(mid+1, r);
val=L->val+R->val;
}else{
val=1;
}
}
void update(int ps){
if(dd==htt){
val=0;
//cout<<ps<<endl;
return ;
}
if(ps<=mid){
L->update(ps);
}else{
R->update(ps);
}
val=L->val+R->val;
}
long long query(int l, int r){
if(dd==l&&r==htt){
return val;
}
else if(r<=mid)return L->query(l, r);
else if(l>mid)return R->query(l, r);
else return L->query(l, mid)+R->query(mid+1, r);
}
};
long long count_swaps(std::vector<int> s) {
long long n = s.size()/2, sum=0;
/*
for(int i = 0 ; i < n ; i++){
sum+=i;
}*/
vector<int>pos[n*2+1];
int conut[n*2+1];
memset(conut, -1, sizeof conut);
//bool contado[n*2+1];
for(int i = 0 ; i < n * 2 ; i++){
//contado[abs(s[i])*2]=false;
if(s[i]>0){//par
pos[s[i]*2].PB(i);
if(conut[s[i]*2]==-1)conut[s[i]*2]=0;
}else{
pos[(-s[i]*2)-1].PB(i);
if(conut[-s[i]*2-1]==-1)conut[(-s[i]*2)-1]=0;
}
}
segtree *tree = new segtree(0, n*2);
for(int i = 0 ; i < n*2 ; i++){
if(s[i]>0){
conut[s[i]*2]++;
s[pos[s[i]*2-1][conut[s[i]*2-1]]]=0;
//cout<<i<<" "<<pos[s[i]*2-1][conut[s[i]*2-1]]<<" = "<<tree->query(i, pos[s[i]*2-1][conut[s[i]*2-1]])<<endl;
sum+=tree->query(i, pos[s[i]*2-1][conut[s[i]*2-1]])-1;
tree->update(pos[s[i]*2-1][conut[s[i]*2-1]]);
//cout<<'s'<<sum<<endl;
conut[s[i]*2-1]++;
}else if(s[i]<0){
conut[-s[i]*2-1]++;
s[pos[-s[i]*2][conut[-s[i]*2]]]=0;
if(i+1<pos[-s[i]*2][conut[-s[i]*2]])sum+=tree->query(i+1, pos[-s[i]*2][conut[-s[i]*2]])-1;
tree->update(pos[-s[i]*2][conut[-s[i]*2]]);
conut[-s[i]*2]++;
//cout<<'s'<<sum<<endl;
}
}
return sum;
}
