题目描述

线条小镇的 $N$ 个居民排成了一条线。最初，居民们从左到右沿着线的幸福值为

$$h_1,h_2,\ldots,h_N.$$

你是线条小镇的镇长，正在实施名为「社区、糖果和组织」（CCO）的计划。因此，你拥有了交换居民位置的权力。

一次操作中，你可以选择两个相邻的居民，交换他们在线中的位置。但是，这次交换会导致这两个居民的幸福值都变为相反数。

你想知道，是否能经过若干次操作，使得居民的幸福值从左到右按非递减顺序排列。如果可以，请输出所需的最少交换次数；如果不可能，请输出 $-1$。

输入格式

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

第二行包含 $N$ 个整数 $h_1,h_2,\ldots,h_N$，表示从左到右每个居民的幸福值。

输出格式

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

样例 1 输入

6
-2 7 -1 -8 2 8

样例 1 输出

3

样例 1 解释

可以进行 $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$ 的方案。

样例 2 输入

4
1 -1 1 -1

样例 2 输出

-1

样例 2 解释

不存在一系列交换，可以使居民的幸福值按非递减顺序排列。

数据范围与子任务

对于所有数据，满足：

$$1 \le N \le 5\times 10^5, \qquad -10^9 \le h_i \le 10^9.$$

子任务编号	分值	$N$ 的范围	额外限制
1	12	$1 \le N \le 2000$	对于所有 $i$，$
2		$1 \le N \le 5\times 10^5$
3		$1 \le N \le 2000$
4	16	$1 \le N \le 5\times 10^5$
5		$1 \le N \le 2000$	对于所有 $i\ne j$，$
6	12	$1 \le N \le 5\times 10^5$
7	8	$1 \le N \le 2000$	没有额外限制
8	12	$1 \le N \le 5\times 10^5$