#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> s) {
int n=s.size()/2;
vector<int> v[2*n+1];
for(int i=2*n-1;i>-1;i--)v[s[i]+n].push_back(i+1);
int bit[2*n+1];
memset(bit,0,sizeof(bit));
auto upd=[&](int l,int r){
int i=l;
while(i<=2*n){
bit[i]++;
i+=i&(-i);
}
if(r==2*n)return;
i=r+1;
while(i<=2*n){
bit[i]--;
i+=i&(-i);
}
};
auto sum=[&](int i){
int s=0;
while(i){
s+=bit[i];
i-=i&(-i);
}
return s;
};
long long ans=0;
for(int i=1;i<=2*n;i+=2){
int l=1,r=2*n;
while(l<r){
int m=(l+r)/2;
if(sum(m)+m>=i)r=m;
else l=m+1;
}
int x=s[l-1];
int idx=v[-x+n].back();
v[-x+n].pop_back();
v[x+n].pop_back();
ans+=(long long)(sum(idx)+idx-1-i+(x>0));
upd(1,idx-1);
}
return ans;
}
