Line Town 的 $N$ 位居民排成一行。最初，居民从左到右的幸福值分别为 $h_1, h_2, \dots, h_N$。
作为 Line Town 的市长，你正在实施名为“社区、糖果与组织”（CCO）的计划的第三大支柱。因此，你行使市长权力来交换居民的位置。在一次交换中，你可以让两个相邻的居民交换位置。然而，这次交换会导致这两位居民的幸福值都变为原来的相反数。
你希望进行若干次交换，使得居民的幸福值从左到右呈非递减顺序排列。请确定这是否可行，如果可行，求出所需的最少交换次数。
输入格式
第一行包含一个整数 $N$。
第二行包含 $N$ 个整数 $h_1, \dots, h_N$ ($-10^9 \le h_i \le 10^9$)，表示从左到右居民的幸福值。
| 分值 | $N$ 的范围 | $h_i$ 的范围 | ||||
|---|---|---|---|---|---|---|
| 3 分 | $1 \le N \le 2\,000$ | $ | h_i | = 1$ 对所有 $i$ 成立 | ||
| 3 分 | $1 \le N \le 500\,000$ | $ | h_i | = 1$ 对所有 $i$ 成立 | ||
| 3 分 | $1 \le N \le 2\,000$ | $ | h_i | \le 1$ 对所有 $i$ 成立 | ||
| 4 分 | $1 \le N \le 500\,000$ | $ | h_i | \le 1$ 对所有 $i$ 成立 | ||
| 4 分 | $1 \le N \le 2\,000$ | $ | h_i | \neq | h_j | $ 对所有 $i \neq j$ 成立 |
| 3 分 | $1 \le N \le 500\,000$ | $ | h_i | \neq | h_j | $ 对所有 $i \neq j$ 成立 |
| 2 分 | $1 \le N \le 2\,000$ | 无附加限制 | ||||
| 3 分 | $1 \le N \le 500\,000$ | 无附加限制 |
输出格式
输出一行，包含最少的交换次数，如果任务无法完成，则输出 $-1$。
样例
输入 1
6 -2 7 -1 -8 2 8
输出 1
3
说明 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
4 1 -1 1 -1
输出 2
-1
说明 2
不存在任何交换序列能使居民的幸福值按非递减顺序排列。