#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define f first
#define s second
#define pii pair<ll,ll>
#define pb push_back
vector<ll> seg;
void build(ll l, ll r, ll v){
if(l>r){
return;
}
if(l==r){
seg[v]=1;
return;
}
ll m=(l+r)/2;
build(l,m,2*v);
build(m+1,r,2*v+1);
seg[v]=seg[2*v]+seg[2*v+1];
}
void update(ll l, ll r, ll v, ll id, ll x){
if(l>r){
return;
}
if(l==r){
seg[v]+=x;
return;
}
ll m=(l+r)/2;
if(id<=m){
update(l,m,2*v,id,x);
}else{
update(m+1,r,2*v+1,id,x);
}
seg[v]=seg[2*v]+seg[2*v+1];
}
ll get(ll l, ll r, ll v, ll cl, ll cr){
if(l>r){
return 0;
}
if(cl>cr){
return 0;
}
if(l==cl and r==cr){
return seg[v];
}
ll m=(l+r)/2;
return get(l,m,2*v,cl,min(m,cr))+get(m+1,r,2*v+1,max(m+1,cl),cr);
}
ll count_swaps(vector<int> s){
ll n=s.size()/2;
vector<ll> left,right;
map<ll,queue<ll>> socks;
for(ll i=0;i<2*n;i++){
if(!socks[-s[i]].empty()){
if(s[i]>0){
right.pb(i);
left.pb(socks[-s[i]].front());
socks[-s[i]].pop();
}else{
left.pb(i);
right.pb(socks[-s[i]].front());
socks[-s[i]].pop();
}
}else{
socks[s[i]].push(i);
}
}
vector<pii> order(n);
ll ans=0;
for(ll i=0;i<n;i++){
ans+=abs(left[i]-right[i])-1;
order[i]={abs(left[i]-right[i]),i};
if(left[i]>right[i]){
ans++;
}
}
sort(order.begin(),order.end());
seg.resize(8*n+5);
build(1,2*n,1);
for(ll i=0;i<n;i++){
ll id=order[i].s;
ll l=min(left[i]+1,right[i]+1);
ll r=max(left[i]+1,right[i]+1);
//cout<<l<<' '<<r<<' '<<get(1,2*n,1,l,r)<<'\n';
update(1,2*n,1,l,-1);
update(1,2*n,1,r,-1);
ans-=get(1,2*n,1,l,r);
}
return ans;
}
