题目描述

译自 CCO 2023 Day1 T3「Line Town」。

线条小镇的 $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

可以进行 $3$ 次交换，如下所示：

1. 交换第 $2$ 和第 $3$ 个居民，幸福值变成了 $[-2,1,-7,-8,2,8]$。
2. 交换第 $4$ 和第 $5$ 个居民，幸福值变成了 $[-2,1,-7,-2,8,8]$。
3. 交换第 $3$ 和第 $4$ 个居民，幸福值变成了 $[-2,1,2,7,8,8]$。

居民们现在按照要求的幸福值非递减的顺序排列了。没有比 $3$ 次更少的交换次数可以得到非递减的排列。

4
1 -1 1 -1

-1

没有一系列的交换可以使居民按照幸福值非递减的顺序排列。

数据范围与提示

对于所有的数据，有 $1\leq N\leq 5\times 10^5$，$-10^{9} \leq h_{i} \leq 10^{9}$。