配点 : 700 点
問題文
一定长度 M 整数序列 给出 B 当满足以下条件时:良好的数列 它被称为 。 满足
- 1 \leq i \lt j \lt M 和 |B_i-B_{i+1}|=|B_j-B_{j+1}| 的一对整数 (i,j) 存在否。
企鹅的目标是达到给定的长度。 对 N 整数序列 给出 A 执行以下操作 通过在 0 上重复任意次数,A 该值应乘以良好的数列 它被称为 。 选择
- 1 \leq l \leq r \leq N 的一对整数 (l,r) ,A_l,A_{l+1},\ldots,A_r 分别 定义 -1 相乘。
判断企鹅君的目标是否可以实现,如果可以的话,找出所需的最少操作次数。
制約
- 3 \leq N \leq 10^5
- -10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 \ldots A_N
出力
如果企鹅君的目标可以实现,则设定最少的操作次数,如果无法实现,则设定最少的操作次数。
最好只执行一次该操作,如 -1 。
入力例 1
4 1 3 0 2
出力例 1
1
例如 第 (l,r)=(2,3) 。
入力例 2
4 -2 1 -4 8
出力例 2
0
企鹅君的目的已经达到了。
入力例 3
4 1 1 1 1
出力例 3
-1
企鹅无法实现他的目标。 编号为
入力例 4
10 -7 4 -8 6 10 3 4 -9 4 7
出力例 4
1
原案: 企鹅人