#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
struct fenwick {
int n; vector<int> bit;
fenwick(int a) : n(a), bit(a+1) {}
void update(int pos, int x) {
pos++;
for (int i = pos; i <= n; i += i&-i) bit[i] += x;
}
int sum(int pos) {
int res = 0;
while (pos) res += bit[pos], pos -= pos&-pos;
return res;
}
int query(int l, int r) {
return sum(r+1) - sum(l);
}
};
long long count_swaps(std::vector<int> s) {
int n = sz(s);
bool sm = 1;
for (int i = 1; i < n; i++) sm &= abs(s[i]) == abs(s[0]);
if (sm) {
fenwick fw(n);
int A = 0, B = 1;
ll inv = 0;
for (int i = 0; i < n; i++) {
int pos;
if (s[i] < 0) pos = A, A += 2;
else pos = B, B += 2;
inv += pos+1 < n ? fw.query(pos+1, n-1) : 0;
fw.update(pos, 1);
}
return inv;
}
if (n / 2 <= 8) {
vector<int> who;
for (int i = 0; i < n; i++) {
if (s[i] < 0) who.emplace_back(s[i]);
}
sort(all(who));
ll ans = 1e18;
do {
vector<bool> vis(n);
vector<int> where(n);
for (int i = 0; i < n; i++) {
int fd = who[i / 2] * (i % 2 == 0 ? 1 : -1);
for (int j = 0; j < n; j++) {
if (s[j] == fd && !vis[j]) {
vis[j] = 1, where[i] = j; break;
}
}
}
ll inv = 0;
for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) inv += where[i] > where[j];
ckmin(ans, inv);
}
while (next_permutation(all(who)));
return ans;
}
return 0;
}
