#include "shoes.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
struct BIT{
int n;
vector<int> bt;
void init(int x){
n=x;
bt.resize(n+1);
}
void update(int x,int y){
for(;x<=n;x+=(x&-x)){
bt[x]+=y;
}
}
int query(int x){
int ans=0;
for(;x>0;x-=(x&-x)){
ans+=bt[x];
}
return ans;
}
};
long long count_swaps(vector<int> s) {
int n=s.size();
long long ans=1e18;
vector<pair<int,int> > nw;
int gg=0;
vector<queue<pair<int,int> > > cnt(n+1);
for(int i=0;i<n;i++){
int u=abs(s[i]);
if(!cnt[u].size() || cnt[u].front().fs==s[i]){
cnt[u].push({s[i],i});
}
else{
nw.push_back({cnt[u].front().sc,i});
if(s[i]<0){
gg++;
}
cnt[u].pop();
}
}
sort(nw.begin(),nw.end());
vector<int> z(n/2);
iota(z.begin(),z.end(),0);
do{
BIT bt;
bt.init(n);
long long nz=0;
for(int i=0;i<n;i++){
bt.update(i+1,1);
}
for(int i=0;i<n/2;i++){
bt.update(nw[z[i]].fs+1,-1);
nz+=bt.query(nw[z[i]].fs+1);
bt.update(nw[z[i]].sc+1,-1);
nz+=bt.query(nw[z[i]].sc+1);
}
ans=min(ans,nz);
break;
}while(next_permutation(z.begin(),z.end()));
return ans+gg;
}
