Public Judge

pjudge

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100

# 21779. 【PR #11】交换

统计

给定一个长度为 $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}$