#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int MAXN = 100000;
int v[2 * MAXN + 1], minp[2 * MAXN + 1];
long long count_swaps(std::vector<int> s) {
//incerc greedy si incep din stanga si vad pe primele 2 pe care nu am deja pereche sa vad ce pereche ar face nr minim de swapuri ca sa ajunga acolo
int n, i, rez2, poz, j, x, n2;
long long rez;
n2 = s.size();
n = n2 / 2;
for (i = 1; i <= n2; i++) {
v[i] = s[i - 1];
if (s[i - 1] < 0) {
v[i] = n - v[i];
}
}
rez = 0;
for (i = 1; i <= n2; i += 2) {
for (j = 1; j <= n2; j++) {
minp[j] = n2 + 1;
}
for (j = n2; j >= i; j--) {
minp[v[j]] = j;
}
rez2 = n2 + 1;
poz = 0;
for (j = 1; j <= n; j++) {
x = minp[j] + minp[n + j] + (minp[j] < minp[n + j]) - 2 * i - 1;//scad unul daca dr este in stanga lui st
if (x < rez2) {
rez2 = x;
poz = j;
}
}
rez += rez2;
for (j = minp[n + poz]; j > i; j--) {
swap(v[j], v[j - 1]);
}
j = minp[poz];
if (minp[poz] < minp[n + poz]) {
j++;
}
for (; j > i + 1; j--) {
swap(v[j], v[j - 1]);
}
}
return rez;
}
