#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> s) {
int n = s.size()/2;
if (n == 0) return 0;
// Compress
set<int> visited;
for (int i = 0; i < 2*n; i++) {
visited.insert(abs(s[i]));
}
map<int, int> mapper;
int idx = 1;
for (auto x : visited) {
mapper[x] = idx++;
}
for (int i = 0; i < 2*n; i++) {
if (s[i] > 0) s[i] = mapper[s[i]];
else s[i] = -mapper[-s[i]];
}
vector<vector<int>> left(n+1), right(n+1);
for (int i = 0; i < 2*n; i++) {
if (s[i] < 0) left[abs(s[i])].push_back(i);
else right[abs(s[i])].push_back(i);
}
int curr = -1, calc = 1e7;
for (int i = 1; i <= n; i++) {
if (left[i].size() == 0) continue;
int tmp = left[i][0]+right[i][0]-((left[i][0] < right[i][0])? 1 : 0);
if (tmp < calc) {
curr = i;
calc = tmp;
}
}
assert(curr != -1);
vector<int> newS;
for (int i = 0; i < 2*n; i++) {
if (i == left[curr][0]) continue;
if (i == right[curr][0]) continue;
newS.push_back(s[i]);
}
return calc + count_swaps(newS);
}
