#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll sub2(vector <int> S) {
int n = S.size() / 2;
vector <int> le[n + 1], ri[n + 1];
vector <pair <int, int>> shoes;
for (int i = 0; i < S.size(); i++) {
if (S[i] < 0) le[-S[i]].emplace_back(i);
else ri[S[i]].emplace_back(i);
}
for (int val = 1; val <= n; val++)
for (int i = 0; i < le[val].size(); i++)
shoes.emplace_back(le[val][i], ri[val][i]);
vector <int> permu(n); iota(permu.begin(), permu.end(), 0);
ll res = 1e18;
do {
ll cost = 0; vector <bool> mark(S.size());
for (int pos = 0; pos < S.size(); pos++) {
int sh = (pos & 1) ? shoes[permu[pos >> 1]].second : shoes[permu[pos >> 1]].first;
int real_sh = sh; mark[sh] = true;
for (int i = sh + 1; i < S.size(); i++) real_sh += mark[i];
cost += abs(real_sh - pos);
}
res = min(res, cost);
} while (next_permutation(permu.begin(), permu.end()));
return res;
}
ll sub3(vector <int> S) {
vector <int> L;
for (int i = 0; i < S.size(); i++)
if (S[i] < 0) L.emplace_back(i);
ll ans = 0;
for (int i = 0; i < L.size(); i++)
ans += abs(L[i] - i * 2);
return ans;
}
ll sub4(vector <int> S) {
int n = S.size() / 2; // 1 + ... + n - 1
return 1ll * n * (n - 1) / 2;
}
ll sub5(vector <int> S) {
int n = S.size() / 2;
vector <int> le[n + 1], ri[n + 1];
vector <pair <int, int>> shoes;
for (int i = 0; i < S.size(); i++) {
if (S[i] < 0) le[-S[i]].emplace_back(i);
else ri[S[i]].emplace_back(i);
}
for (int val = 1; val <= n; val++)
for (int i = 0; i < le[val].size(); i++)
shoes.emplace_back(le[val][i], ri[val][i]);
sort (shoes.begin(), shoes.end(), [&] (pair <int, int> u, pair <int, int> v) {
return min(u.first, u.second) < min(v.first, v.second);
});
ll cost = 0; vector <bool> mark(S.size());
for (int pos = 0; pos < S.size(); pos++) {
int sh = (pos & 1) ? shoes[pos >> 1].second : shoes[pos >> 1].first;
int real_sh = sh; mark[sh] = true;
for (int i = sh + 1; i < S.size(); i++) real_sh += mark[i];
cost += abs(real_sh - pos);
}
return cost;
}
struct FenwickTree {
vector <int> bit;
FenwickTree () {}
FenwickTree (int sz) {
bit.assign(sz + 1, 0);
}
void update(int p, int val) {
for (; p < bit.size(); p += p & -p) bit[p] += val;
}
int get(int p) {
int res = 0; for (; p > 0; p -= p & -p) res += bit[p];
return res;
}
};
ll sub6(vector <int> S) {
int n = S.size() / 2;
vector <int> le[n + 1], ri[n + 1];
vector <pair <int, int>> shoes;
for (int i = 0; i < S.size(); i++) {
if (S[i] < 0) le[-S[i]].emplace_back(i);
else ri[S[i]].emplace_back(i);
}
for (int val = 1; val <= n; val++)
for (int i = 0; i < le[val].size(); i++)
shoes.emplace_back(le[val][i], ri[val][i]);
sort (shoes.begin(), shoes.end(), [&] (pair <int, int> u, pair <int, int> v) {
return min(u.first, u.second) < min(v.first, v.second);
});
FenwickTree fen(S.size()); ll cost = 0;
for (int pos = 0; pos < S.size(); pos++) {
int sh = (pos & 1) ? shoes[pos >> 1].second : shoes[pos >> 1].first;
int real_sh = sh + fen.get(S.size()) - fen.get(sh + 1); fen.update(sh + 1, 1);
cost += abs(real_sh - pos);
}
return cost;
}
ll count_swaps(vector <int> S) {
if (S.size() == 2) return (S[0] > 0); // sub1
bool s3 = true;
for (int i = 1; i < S.size(); i++)
if (abs(S[i - 1]) != abs(S[i])) s3 = false;
if (s3) return sub3(S); // sub3
bool s4 = true;
for (int i = 0; i < S.size() / 2; i++)
if (S[i] > 0 || S[i + S.size() / 2] < 0 || abs(S[i]) != abs(S[i + S.size() / 2]))
s4 = false;
if (s4) return sub4(S); // sub4
if (S.size() <= 16) return sub2(S); // sub2
if (S.size() <= 2000) return sub5(S); // sub5
return sub6(S);
}
#ifdef cute
int main() {
cout << count_swaps({2, 1, -1, -2});
}
#endif
