给定一个长度为 $n$ 的序列 $h_1,\cdots,h_n$ ，你可以进行若干次如下操作：
- 选择一个位置 $i$ ，满足 $1\le i\le n-1$ ；
- 令 $h'_i=-h_{i+1},h'_{i+1}=-h_i$ ，保持其他位置不变。
你需要使得操作结束时 $h$ 单调不降。判断是否存在合法方案，并且如果存在，最小化操作次数。
输入格式
第一行一个正整数 $n$ ，表示序列长度。
第二行 $n$ 个整数 $h_1,\cdots,h_n$ 。
输出格式
如果不存在合法方案，输出一行 -1 。否则输出一行一个非负整数，表示最小操作次数。
样例一
input
6 -2 7 -1 -8 2 8
output
3
explanation
选择的 $i$ 依次是 $2,4,3$ 。
样例二
input
4 1 -1 1 -1
output
-1
数据范围
对于所有数据，保证 $1\le n\le 5\times 10^5, -10^9\le h_i\le 10^9$ 。
| 子任务编号 | $n\le $ | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $2000$ | $\lvert h_i\rvert=1$ | $10$ |
| $2$ | $5\times 10^5$ | $\lvert h_i\rvert=1$ | $10$ |
| $3$ | $2000$ | $\lvert h_i\rvert\le 1$ | $10$ |
| $4$ | $5\times 10^5$ | $\lvert h_i\rvert\le 1$ | $14$ |
| $5$ | $2000$ | $\lvert h_i\rvert$ 两两不同 | $20$ |
| $6$ | $5\times 10^5$ | $\lvert h_i\rvert$ 两两不同 | $16$ |
| $7$ | $2000$ | $ $ | $8$ |
| $8$ | $5\times 10^5$ | $ $ | $12$ |
时间限制：$\texttt{2s}$
空间限制：$\texttt{2048MB}$