#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pi pair<int,int>
long long count_swaps(vector<int> s) {
ll ans = 1e18;
int n = s.size();
vector<pi> lefts(n/2);
int cntleft = 0;
vector<pair<int, pi>> sortlefts(n/2);
vector<queue<int>> rightinds(n);
set<int> shoes;
for(int i =0; i<n ;i++){
shoes.insert({i, i});
if(s[i] > 0){
rightinds[s[i]].push(i);
}
}
for(int i =0; i<n; i++){
if(s[i] < 0){
int firstright = rightinds[-s[i]].front();
rightinds[-s[i]].pop();
lefts[cntleft++] = {i, firstright};
sortlefts[cntleft - 1] = {i+firstright, {i, firstright}};
}
}
sort(sortlefts.begin(), sortlefts.end());
for(int i =0; i<n/2; i++){
lefts[i] = sortlefts[i].second;
}
ll posans = 0;
vector<int> inds(n);
for(int i =0; i<n ;i++) inds[i] = i;
//for(int i =0; i<n/ 2; i++) cout << lefts[i]<<", "; cout <<endl;
int l = 0;
for(pi shoe : lefts){
//get first availabe
int leftind = shoe.first;
int rightind = shoe.second;
//cout <<endl;
int newleftind = 2 * l;
int cnt = 0;
for(int ss : shoes){
if(ss == leftind){
newleftind += cnt;
}
cnt++;
}
ll dist1 = abs(newleftind - 2 * l);
shoes.erase(shoes.find(leftind));
int newrightind = 2 * l + 1;
cnt = 0;
for(int ss : shoes){
if(ss == rightind){
newrightind += cnt;
}
cnt++;
}
//cout <<leftind<<", "<<rightind<<": "<< newleftind<<", "<<newrightind<<endl;
ll dist2 = abs(newrightind -( 2 * l + 1));
shoes.erase(shoes.find(rightind));
/*for(int ss : shoes){
cout <<ss<<", ";
}
cout <<endl;
*/
//cout << inds[lefts[l]]<<", "<<inds[firstright]<<": ";
//cout << lefts[l]<<", "<<firstright<<": "<<dist1<<", "<<dist2<<endl;
posans += dist1 + dist2;
l++;
}
ans = min(ans, posans);
//cout << posans<<endl<<endl;
return ans;
}
/***********/
