#include "shoes.h"
#include<bits/stdc++.h>
using namespace std ;
vector<int > pos[200005];
vector<int>st ;
int idx ;
int binarysearch(int u){ sort(st.begin() , st.end());
while(st.size() && st.back() > idx)st.pop_back();
if(st.empty())return 0 ;
if(st.back() < u)return 0 ;
int l = 0 , r = st.size() , md ;
while(l < r){
md = (l + r) / 2 ;
if(st[md] < u)l = md + 1 ;
else r = md ;
}
return st.size() - l ;
}
long long count_swaps(vector<int> v) {
int n = v.size() / 2 ;
for(int i = 0 ; i < n * 2 ; i ++){
pos[v[i] + n] .push_back(i) ;
}
long long ans = 0 ;
for(int i = 2 * n - 1 ; i >= 0 ; i --){
if(v[i] == 0)continue ;
idx = i ;
int p = v[i] * -1 + n ;
pos[v[i] + n].pop_back();
auto u = binarysearch(p);
int sum = 0 ;
v[pos[p].back()] = 0;
sum = u ;
sum = i - pos[p].back() - sum - 1 ;
st.push_back(pos[p].back());
pos[p].pop_back();
sum += (v[i] < 0);
ans += sum ;
}
return ans;
}
