#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define ll long long
#define pb push_back
struct segtree{
int n;
vector<int>d;
vector<int>u;
segtree(vector<int>v){
n=v.size();
u=v;
d.resize(4*n);
build(1,0,n-1);
}
void build(int node,int l,int r){
if(l==r){
d[node]=u[l];
return;
}
int mid=(l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
d[node]=d[node*2]+d[node*2+1];
}
int query(int node,int l,int r,int L,int R){
if(L > r || R < l || L > R){
return 0;
}
if(L <= l && r <= R){
return d[node];
}
int mid=(l+r)/2;
return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
}
void update(int node,int l,int r,int k,int val){
if(l>k || r<k)return;
if(l==r){
d[node]=val;
return;
}
int mid=(l+r)/2;
update(node*2,l,mid,k,val);
update(node*2+1,mid+1,r,k,val);
d[node]=d[node*2]+d[node*2+1];
}
};
long long count_swaps(vector<int>s){
int n=s.size()/2;//number of pair
vector<int>pos[n+5];//add
vector<int>neg[n+5];
for(int i=0;i<2*n;i++){
if(s[i]<0){
neg[-s[i]].pb(i);
}
else{
pos[s[i]].pb(i);
}
}
int cur=0;
long long ans=0;
vector<int>a(2*n);
for(int i=1;i<=n;i++){
for(int j=0;j<pos[i].size();j++){
cur++;
if(pos[i][j]<neg[i][j]){
ans++;
}
a[neg[i][j]]=cur;
a[pos[i][j]]=cur;
}
}
vector<int>fi,se;
fi.resize(2*n);
se.resize(2*n);
int l[n+5],r[n+5];
fill(l+1,l+n+1,-1);
for(int i=0;i<2*n;i++){
if(l[a[i]]==-1){
l[a[i]]=i;
fi[i]=1;
se[i]=0;
}
else{
r[a[i]]=i;
fi[i]=0;
se[i]=1;
}
}
segtree sg1(fi);
segtree sg2(se);
for(int i=0;i<2*n;i++){
if(l[a[i]]==-1){
continue;
}
ans+=sg1.query(1,0,2*n-1,l[a[i]],r[a[i]]);
ans-=sg2.query(1,0,2*n-1,l[a[i]],r[a[i]]);
sg1.update(1,0,2*n-1,l[a[i]],0);
sg2.update(1,0,2*n-1,r[a[i]],0);
l[a[i]]=-1;
}
return ans;
}
