#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MID ((l+r)/2)
struct node{
ll val;
node *L, *R;
void init(ll l, ll r){
val=0;
if(l!=r){
L=new node;
L->init(l,MID);
R=new node;
R->init(MID+1,r);
}
}
void upd(ll l, ll r, ll i){
if(l==i && i==r){
val=1;
}
else if(l<=i && i<=r){
val++;
L->upd(l,MID,i);
R->upd(MID+1,r,i);
}
}
ll ans(ll l, ll r, ll tl, ll tr){
if(tl<=l && r<=tr) return val;
else if(r<tl || tr<l) return 0;
else return L->ans(l,MID,tl,tr) + R->ans(MID+1,r,tl,tr);
}
};
long long count_swaps(vector<int> s){
ll n=s.size()/2;
queue<ll> l[n+1], r[n+1];
ll c=0;
for(ll i=0; i<2*n; i++){
if(s[i]<0){
l[-s[i]].push(2*c);
r[-s[i]].push(2*c+1);
// cout<<-s[i]<<" "<<2*i<<endl;
c++;
}
}
// cout<<"ok1"<<endl;
vector<ll> s2;
ll pos[2*n];
for(ll i=0; i<2*n; i++){
if(s[i]<0){
s2.push_back(l[-s[i]].front());
pos[l[-s[i]].front()]=s2.size()-1;
l[-s[i]].pop();
}
else{
s2.push_back(r[s[i]].front());
pos[r[s[i]].front()]=s2.size()-1;
r[s[i]].pop();
}
}
// cout<<"ok2"<<endl;
node seg;
seg.init(0,2*n-1);
// cout<<"ok3"<<endl;
ll ans=0;
for(ll i=2*n-1; i>=0; i--){
// cout<<i<<endl;
ans+=seg.ans(0,2*n-1,0,pos[i]);
seg.upd(0,2*n-1,pos[i]);
// cout<<i<<endl;
}
return ans;
}
