#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
/*** Basic Fenwick tree template ***/
struct Fenwick_Tree {
int n;
vector<int> tree; // # parameters
Fenwick_Tree(int _n) { // # initial defining parameters
n = _n + 5, tree.assign(n << 2, 0);
}
inline void add(int idx, int val) { // # add function makes all elements in interval [idx; MAX] +val
for (int i = idx; i <= (n << 1); i += i & -i) tree[i] += val;
}
inline int get(int idx) { // # get function returns value of position idx
int res = 0;
for (int i = idx; i >= 1; i -= i & -i) res += tree[i];
return res;
}
};
long long count_swaps(vector<int> a) {
int N = (int)a.size() >> 1;
int64_t ans = INT_MAX;
Fenwick_Tree BIT(N << 1);
// 1 based indexed..
vector<int> A((N << 1) + 5), L, R; for (int i = 0; i < (N << 1); i++) {
A[i + 1] = a[i];
if (A[i + 1] < 0) L.push_back(i + 1);
else R.push_back(i + 1);
}
auto isIn = [&](array<int, 2> x, array<int, 2> y) -> bool {
if (x[0] > x[1]) return false;
if (y[0] > y[1]) return false;
if (x[0] <= y[0] && y[0] <= x[1] && x[1] <= y[1]) return true;
swap(x, y);
if (x[0] <= y[0] && y[0] <= x[1] && x[1] <= y[1]) return true;
return false;
};
do {
int64_t total = 0, res, i = 0;
while (i < N) {
res = 0;
int li = L[i], ri = R[i];
if (li < ri) {
res = ri - li - 1;
} else {
res = li - ri;
}
for (int j = 0; j < i; j++) {
int lj = L[j], rj = R[j];
res -= isIn({min(li, ri), max(li, ri)}, {min(lj, rj), max(lj, rj)});
}
total += res, i++;
}
ans = min(ans, total);
} while (next_permutation(L.begin(), L.end()));
return ans;
}
