P10068 [CCO 2023] Line Town

线条小镇的 $N$ 个居民排成了一条线。最初，居民们从左到右沿着线的幸福值为 $h_{1}, h_{2}, \ldots, h_{N}$。 你是线条小镇的镇长，你正在实施你的名为「社区、糖果和组织」（CCO）的计划。因此，你拥有了交换居民位置的权力。在一次交换中，你可以让两个相邻的居民交换他们在线中的位置。但是，这次交换会导致两个居民的幸福值取反。 你想要知道是否能进行一些交换，使得居民的幸福值从左到右按非递减的顺序排列。如果可能，需要的最少交换次数是多少。

第一行包含一个整数 $N$。 第二行包含 $N$ 个整数 $h_{1}, \ldots, h_{N}$，表示从左到右的居民的幸福值。

输出一行一个整数，表示最少的交换次数，如果任务不可能完成输出 $-1$。

**样例解释 1** 可以进行 3 次交换，如下所示： - 交换第 2 和第 3 个居民，幸福值变成了 $[-2,1,-7,-8,2,8]$。 - 交换第 4 和第 5 个居民，幸福值变成了 $[-2,1,-7,-2,8,8]$。 - 交换第 3 和第 4 个居民，幸福值变成了 $[-2,1,2,7,8,8]$。 居民们现在按照要求的幸福值非递减的顺序排列了。没有比 3 次更少的交换次数可以得到非递减的排列。 **样例解释 2** 没有一系列的交换可以使居民按照幸福值非递减的顺序排列。 对于所有的数据，有 $1\leq N\leq 5\times 10^5，-10^{9} \leq h_{i} \leq 10^{9}$。 - 额外限制 A：对于所有的 $i$，$\left|h_{i}\right| = 1$。 - 额外限制 B：对于所有的 $i$，$\left|h_{i}\right| \leq 1$。 - 额外限制 C：对于所有的 $i \neq j$，$\left|h_{i}\right| \neq\left|h_{j}\right|$。 子任务编号| 分值| $N$ 的范围 |额外限制| |:-:|:-:|:-:|:-:| | 1 |12| $1 \leq N \leq 2000$ |A| |2 |12 |$1 \leq N \leq 5\times 10^5$|A| |3 |12| $1 \leq N \leq 2000$|B | |4 |16 |$1 \leq N \leq 5\times 10^5$|B| |5 |16 |$1 \leq N \leq 2000$| C| |6 |12 |$1 \leq N \leq 5\times 10^5$|C | |7|8 |$1 \leq N \leq 2000$ | | |8|12 |$1 \leq N \leq 5\times 10^5$ | |