#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int MAXN = 100000;
int v[2 * MAXN + 1], minp[2 * MAXN + 1], sp[2 * MAXN + 2];
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];
}
}
//in loc sa dau swap doar pun 0 pe acea pozitie si tin sp cu cate valori de 0 sunt pe prefix
rez = 0;
for (i = 1; i <= n2; i += 2) {
for (j = 1; j <= n2; j++) {
minp[j] = n2 + 1;
}
for (j = n2; j >= 1; 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]) - 3 - sp[minp[j]] - sp[minp[n + j]];//scad unul daca dr este in stanga lui st
if (minp[j] <= n2 && minp[n + j] <= n2 && x < rez2) {
rez2 = x;
poz = j;
}
}
rez += rez2;
v[minp[n + poz]] = v[minp[poz]] = 0;
for (j = minp[n + poz]; j <= n2; j++) {
sp[j]++;
}
for (j = minp[poz]; j <= n2; j++) {
sp[j]++;
}
}
return rez;
}
