#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){
ll ans=0;
ll n=s.size()/2;
vector<int>vec(2*n,1);
segtree sg(vec);
ll cur[n+5];
fill(cur,cur+n+1,0);
vector<int>r[n+5];
vector<int>l[n+5];
for(ll i=0;i<s.size();i++){
if(s[i]>=0){
r[s[i]].pb(i);
}
else{
l[-s[i]].pb(i);
}
}
int check[2*n+5];
fill(check,check+2*n+1,0);
for(int i=0;i<2*n;i++){
if(check[i]==0){
int pr;
if(s[i]>0){
ans++;
pr=l[s[i]][cur[abs(s[i])]];
}
else{
pr=r[-s[i]][cur[abs(s[i])]];
}
cur[abs(s[i])]++;
check[i]=1;
check[pr]=1;
int add=sg.query(1,0,2*n-1,i+1,pr-1);
ans+=add;
sg.update(1,0,2*n-1,i,0);
sg.update(1,0,2*n-1,pr,0);
}
}
return ans;
}
