#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;
const ll MAXN = 1e5+5;
const ll INF = 1e9+7;
ll seg[8*MAXN];
void recalculate(ll node){
seg[node] = seg[2*node+1]+seg[2*node+2];
}
void build(ll node, ll left, ll right){
if(left==right){
seg[node]=0;
}else{
ll middle = (left+right)/2;
build(2*node+1,left,middle);
build(2*node+2,middle+1,right);
recalculate(node);
}
}
void update(ll node, ll left, ll right, ll pos){
//cout<<node<<" "<<left<<" "<<right<<" "<<pos<<endl;
if(left==right){
seg[node]=1;
}else{
ll middle = (left+right)/2;
if(pos<=middle)update(2*node+1,left,middle,pos);
if(pos>=middle+1)update(2*node+2,middle+1,right,pos);
recalculate(node);
}
}
ll querie(ll node, ll left, ll right,ll a, ll b){
if(a<=left&&b>=right){
return seg[node];
}
ll middle = (left+right)/2,res=0;
if(a<=middle)res+=querie(2*node+1,left,middle,a,b);
if(b>=middle+1)res+=querie(2*node+2,middle+1,right,a,b);
return res;
}
long long count_swaps(std::vector<int> s){
ll n = s.size(),i,j,k; n/=2;
ll match[2*n+2];
vector<vector<ll>>last(2*n+1);
for(i=0;i<2*n;i++){
if(s[i]>0){
last[s[i]].pb(i);
}else{
last[-s[i]+n].pb(i);
}
}
for(i=1;i<=n;i++){
for(k=0;k<(ll)last[i].size();k++){
// cout<<last[i][k]<<" "<<last[i+n][k]<<" ";
match[last[i][k]]=last[i+n][k];
match[last[i+n][k]]=last[i][k];
}
}
build(0,1,2*n);
ll done=0,ans=0;
for(i=0;i<2*n;i++){//cout<<match[i]<<" ";
if(match[i]<i)continue;
done = querie(0,1,2*n,i+1,match[i]+1);
ans += (match[i]-i-1-done);
// cout<<i<<" "<<done<<" "<<match[i]-i-1-done<<endl;
if(s[i]>0)ans++;
update(0,1,2*n,i+1);//este e opcional
update(0,1,2*n,match[i]+1);
}
// for(j=0;j<7;j++)cout<<j<<" "<<seg[j]<<endl;
return ans;
}
