#include "shoes.h"
#include <set>
#include <map>
#include <climits>
#include <iostream>
#include <assert.h>
using namespace std;
long long count_swaps(std::vector<int> s) {
int n = s.size() / 2;
long long ans = 0;
multiset<int> se;
for(int &x: s) {
if(x > 0) se.insert(x);
}
for(int i = 0;i<n*2;i+=2) {
// get to 0
map<int,int> posL, posR;
for(int j = i;j<(int)s.size();j++) {
if(s[j] < 0) {
if(posL.count(s[j]) == 0) posL[s[j]] = j;
else posL[s[j]] = min(posL[s[j]], j);
}else {
if(posR.count(s[j]) == 0) posR[s[j]] = j;
else posR[s[j]] = min(posR[s[j]], j);
}
}
int which = -1;
int mn = INT_MAX;
for(auto yo: posL) {
int cst = (yo.second - i) + (posR[-yo.first] - i);
if(yo.second < posR[-yo.first]) cst--;
if(cst < mn) {
which = yo.first;
mn = cst;
}
}
int L = posL[which];
int R = posR[-which];
if(posL[which] < posR[-which]) {
s.erase(s.begin() + posL[which]);
s.erase(s.begin() + posR[-which] - 1);
}else {
assert(posR[-which] < posL[which]);
s.erase(s.begin() + posR[-which]);
s.erase(s.begin() + posL[which] - 1);
}
s.insert(s.begin() + i, which);
s.insert(s.begin() + i+1, -which);
ans += mn;
// cout << "which = " << which << endl;
// for(int &x: s) cout << x << " ";
// cout << endl;
}
return ans;
}
// . . . . . -1 -2 2 ...... 1
// pos[-1] + pos[1]
// min(pos[-L] + pos[+L])
// h j k l -1 1
// 5
// -x +x -> pos[-x] + pos[x] - 1
// +x -x -> pos[-x] + pos[x]
// // .... 1. -
// int main() {
// cout << count_swaps({-2, 2, 2, -2, -2, 2}) << endl;
// return 0;
// }
