题目描述

线条小镇的 $N$ 个居民排成了一条线。最初，居民们从左到右沿着线的幸福值为 $h_{1}, h_{2}, \ldots, h_{N}$。

你是线条小镇的镇长，你正在实施你的名为「社区、糖果和组织」（CCO）的计划。因此，你拥有了交换居民位置的权力。在一次交换中，你可以让两个相邻的居民交换他们在线中的位置。但是，这次交换会导致两个居民的幸福值取反。

你想要知道是否能进行一些交换，使得居民的幸福值从左到右按非递减的顺序排列。如果可能，需要的最少交换次数是多少。

输入格式

第一行包含一个整数 $N$。

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

输出格式

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

6
-2 7 -1 -8 2 8

3

4
1 -1 1 -1

-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|$。