给定一个长度为 n 的序列 h1,⋯,hn ，你可以进行若干次如下操作：
- 选择一个位置 i ，满足 1≤i≤n−1 ；
- 令 h′i=−hi+1,h′i+1=−hi ，保持其他位置不变。
你需要使得操作结束时 h 单调不降。判断是否存在合法方案，并且如果存在，最小化操作次数。
输入格式
第一行一个正整数 n ，表示序列长度。
第二行 n 个整数 h1,⋯,hn 。
输出格式
如果不存在合法方案，输出一行 -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≤n≤5×105,−109≤hi≤109 。
| 子任务编号 | n≤ | 特殊性质 | 分值 |
|---|---|---|---|
| 1 | 2000 | |hi|=1 | 10 |
| 2 | 5×105 | |hi|=1 | 10 |
| 3 | 2000 | |hi|≤1 | 10 |
| 4 | 5×105 | |hi|≤1 | 14 |
| 5 | 2000 | |hi| 两两不同 | 20 |
| 6 | 5×105 | |hi| 两两不同 | 16 |
| 7 | 2000 | 8 | |
| 8 | 5×105 | 12 |
时间限制：2s
空间限制：2048MB