# [CCO2023] Line Town

## 题目描述

线条小镇的 $N$ 个居民排成了一条线。最初，居民们从左到右沿着线的幸福值为 $h_{1}, h_{2}, \ldots, h_{N}$。

你是线条小镇的镇长，你正在实施你的名为「社区、糖果和组织」（CCO）的计划。因此，你拥有了交换居民位置的权力。在一次交换中，你可以让两个相邻的居民交换他们在线中的位置。但是，这次交换会导致两个居民的幸福值取反。

你想要知道是否能进行一些交换，使得居民的幸福值从左到右按非递减的顺序排列。如果可能，需要的最少交换次数是多少。

## 输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $h_{1}, \ldots, h_{N}$，表示从左到右的居民的幸福值。

## 输出格式

输出一行一个整数，表示最少的交换次数，如果任务不可能完成输出 $-1$。

## 样例 #1

### 样例输入 #1

```
6
-2 7 -1 -8 2 8
```

### 样例输出 #1

```
3
```

## 样例 #2

### 样例输入 #2

```
4
1 -1 1 -1
```

### 样例输出 #2

```
-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$ |	|