这题的特殊性质很有引导性，会了全部特殊性质基本就会正解了。

首先考虑 $|a_i|$ 互不相同怎么做。

发现一个数最后的符号只和它移动距离的奇偶性和原来的符号有关，并且最终序列的绝对值是先递减后递增。

那么自然考虑，按绝对值从大到小，在序列两端填数。设 $f_{i, 0/1}$ 表示考虑了绝对值 $\ge i$ 的数，序列左端填了偶数个 / 奇数个数，的最小交换次数。交换次数就是它在原序列中左边或右边（左边还是右边取决于它被填到最左边还是最右边）比它小的数的个数。时间复杂度 $O(n \log n)$，获得 $\frac{7}{25}$ 的高分。

再考虑 $|a_i| \le 1$ 怎么做。容易想到枚举最终有 $i$ 个 $0$ 换到最左边，但是这样仍然不好直接写出操作次数，因为交换就会变号比较麻烦。

那么有一个处理翻转相邻两位奇偶性的、比较经典的 trick 是翻转奇数位，到这题就是翻转奇数位的符号。这样的好处是操作变成直接交换相邻两个数，不用变号。

现在最终的状态形如 $1, -1, \cdots 1, -1, 0, \cdots, 0, -1, 1, \cdots, -1, 1$，其中最后一位是 $1$ 还是 $-1$ 取决于 $n$ 的奇偶性。那么我们枚举了 $i$ 之后，序列中每一个 $1$ 和 $-1$ 的最终相对位置（在所有 $\pm 1$ 中是从左往右第几个）都能算出来。

那么算交换次数就是 $\pm 1$ 和 $0$ 的交换次数，加上 $\pm 1$ 内部的交换次数。$\pm 1$ 和 $0$ 的交换次数等于一个 $\pm 1$ 左边或右边（左边还是右边取决于它被填到最左边还是最右边）$0$ 的个数，$\pm 1$ 内部的交换次数就是每个 $\pm 1$ 原来的相对位置减去最终的相对位置绝对值之和。

不难通过一些预处理做到 $O(n)$。拼上 $|a_i|$ 互不相同的做法，获得 $\frac{20}{25}$ 的高分。

那么做到这一步其实可以发现正解就是上面两个做法拼起来。仍然是按 $|a_i|$ 从大到小 DP，设当前考虑的绝对值是 $k$，把 $k$ 看成 $1$，$-k$ 看成 $-1$，绝对值 $< k$ 的数看成 $0$，然后套用 $|a_i| \le 1$ 的做法即可。

实现时要特别小心奇偶性的处理。

最终总时间复杂度 $O(n \log n)$，但是除了离散化和计算每个数左边（和右边）比它小的数的个数时间复杂度是 $O(n \log n)$ 之外，其他的部分都是 $O(n)$ 的。

:::info[代码]

// Problem: P10068 [CCO 2023] Line Town
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10068
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

namespace IO {
	const int maxn = 1 << 20;
	
	char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

	inline char gc() {
		return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
	}

	template<typename T = int>
	inline T read() {
		char c = gc();
		T x = 0;
		bool f = 0;
		while (c < '0' || c > '9') {
			f |= (c == '-');
			c = gc();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c ^ 48);
			c = gc();
		}
		return f ? ~(x - 1) : x;
	}
	
	inline int reads(char *s) {
		char c = gc();
		int len = 0;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c) && c != -1) {
			s[len++] = c;
			c = gc();
		}
		s[len] = '\0';
		return len;
	}
	
	inline string reads() {
		char c = gc();
		string s;
		while (isspace(c)) {
			c = gc();
		}
		while (!isspace(c) && c != -1) {
			s += c;
			c = gc();
		}
		return s;
	}

	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	
	struct Flusher {
		~Flusher() {
			flush();
		}
	} AutoFlush;

	inline void pc(char ch) {
		if (oS == obuf + maxn) {
			flush();
		}
		*oS++ = ch;
	}
	
	inline void write(char *s) {
		for (int i = 0; s[i]; ++i) {
			pc(s[i]);
		}
	}
	
	inline void write(const char *s) {
		for (int i = 0; s[i]; ++i) {
			pc(s[i]);
		}
	}

	template<typename T>
	inline void write(T x) {
		static char stk[64], *tp = stk;
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != stk) {
			pc((*--tp) | 48);
		}
	}
	
	template<typename T>
	inline void writesp(T x) {
		write(x);
		pc(' ');
	}
	
	template<typename T>
	inline void writeln(T x) {
		write(x);
		pc('\n');
	}
}

using IO::read;
using IO::reads;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 500100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

int n, a[maxn], lsh[maxn], tot, ls[maxn], rs[maxn], b[maxn], c[maxn], d[maxn];
ll f1[maxn], f2[maxn], f3[maxn], f4[maxn], pre[2][maxn], suf[2][maxn];
bool vis[maxn];
vector<int> ap[maxn];

namespace BIT {
	int c[maxn];
	
	inline void update(int x, int d) {
		for (int i = x; i <= tot; i += (i & (-i))) {
			c[i] += d;
		}
	}
	
	inline int query(int x) {
		int res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res += c[i];
		}
		return res;
	}
}

void solve() {
	n = read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		if (a[i] < 0) {
			a[i] = -a[i];
			vis[i] = 1;
		}
		lsh[++tot] = a[i];
	}
	sort(lsh + 1, lsh + tot + 1);
	tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
	for (int i = 1; i <= n; ++i) {
		a[i] = lower_bound(lsh + 1, lsh + tot + 1, a[i]) - lsh;
		++b[a[i]];
	}
	for (int i = 1; i <= tot; ++i) {
		b[i] += b[i - 1];
	}
	for (int i = 1; i <= n; ++i) {
		ls[i] = BIT::query(a[i] - 1);
		rs[i] = b[a[i] - 1] - ls[i];
		BIT::update(a[i], 1);
	}
	mems(b, 0);
	for (int i = 1; i <= n; ++i) {
		if (vis[i] ^ (i & 1)) {
			a[i] = -a[i];
		}
		ap[abs(a[i])].pb(i);
	}
	ll f[2] = {0, inf};
	int r = n;
	for (int k = tot; k; --k) {
		if (lsh[k] == 0) {
			break;
		}
		ll g[2] = {inf, inf};
		int m1 = 0, m2 = 0, cnt = 0;
		for (int i : ap[k]) {
			++cnt;
			if (a[i] > 0) {
				b[++m1] = i;
				d[i] = cnt;
			} else {
				c[++m2] = i;
				d[i] = cnt;
			}
		}
		for (int i = 1; i <= m1; ++i) {
			f1[i] = f1[i - 1] + ls[b[i]];
			f2[i] = f2[i - 1] + rs[b[i]];
			b[i] = d[b[i]];
		}
		for (int i = 1; i <= m2; ++i) {
			f3[i] = f3[i - 1] + ls[c[i]];
			f4[i] = f4[i - 1] + rs[c[i]];
			c[i] = d[c[i]];
		}
		for (int j = 0; j <= 1; ++j) {
			for (int i = 1, p1 = 1, p2 = 1; i <= m1 + m2; ++i) {
				pre[j][i] = pre[j][i - 1];
				if ((j ^ i) & 1) {
					pre[j][i] += abs(b[p1++] - i);
				} else {
					pre[j][i] += abs(c[p2++] - i);
				}
			}
		}
		suf[0][m1 + m2 + 1] = suf[1][m1 + m2 + 1] = 0;
		for (int j = 0; j <= 1; ++j) {
			for (int i = m1 + m2, o = (r & 1) ^ j, p1 = m1, p2 = m2; i; --i, o ^= 1) {
				suf[j][i] = suf[j][i + 1];
				if (o) {
					suf[j][i] += abs(c[p2--] - i);
				} else {
					suf[j][i] += abs(b[p1--] - i);
				}
			}
		}
		for (int j = 0; j <= 1; ++j) {
			for (int i = 0; i <= m1 + m2; ++i) {
				int x = (i + 1) >> 1, y = (i >> 1);
				if (j) {
					swap(x, y);
				}
				int rx = m1 - x, ry = m2 - y;
				if (rx < 0 || ry < 0) {
					continue;
				}
				if ((r ^ j) & 1) {
					if (rx != ry && rx + 1 != ry) {
						continue;
					}
				} else {
					if (rx != ry && rx != ry + 1) {
						continue;
					}
				}
				g[(i & 1) ^ j] = min(g[(i & 1) ^ j], f[j] + ((((f1[x] + f3[y] + f2[m1] - f2[x] + f4[m2] - f4[y]) << 1) + pre[j][i] + suf[j][i + 1]) >> 1));
			}
		}
		f[0] = g[0];
		f[1] = g[1];
		r -= (int)ap[k].size();
	}
	writeln(min(f[0], f[1]) > 1e18 ? -1 : min(f[0], f[1]));
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

:::