题目描述

译自 $CCO$ $2023$ $Day1$ $T3$「$Line$ $Town$」。

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

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

你需要判断是否能通过若干次交换，使得居民的幸福值从左到右按非递减的顺序排列。如果可能，输出所需的最少交换次数；如果不可能，输出 $-1$。

输入格式

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

输出格式

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

样例 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]$。 此时居民幸福值按非递减顺序排列，且不存在更少交换次数的方案。

样例 2

输入

4
1 -1 1 -1

输出

-1

说明

没有任何一系列交换能使居民的幸福值按非递减顺序排列。

数据范围与提示

• 对于所有数据，$1 \leq N \leq 5 \times 10^5$，$-10^9 \leq h_i \leq 10^9$。
• 子任务信息如下：