#include "shoes.h" #include<bits/extc++.h> #include<bits/stdc++.h> using namespace __gnu_pbds; using namespace std; queue<int> otherpos[100100]; long long calc(vector<int>v){ long long ans=0; int K=0; tree<int,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update>st; for(auto i:v) { st.insert(i); ans+=K++-st.order_of_key(i); } return ans; } long long count_swaps(std::vector<int> s) { long long ans=1e9; int n=s.size()>>1; vector<int>sup; sup.resize(2*n); vector<int>perm(n); iota(perm.begin(),perm.end(),0); do { int CC=0; for(int i=0;i<n*2;i++) if(s[i]<0) sup[i]=2*perm[CC], otherpos[-s[i]].push(2*perm[CC++]+1); for(int i=0;i<n*2;i++)if(s[i]>0) sup[i]=otherpos[s[i]].front(),otherpos[s[i]].pop(); ans=min(ans,calc(sup)); } while(next_permutation(perm.begin(),perm.end())); return ans; }