← 返回题目列表

AtCoder · tkppc6_2_g

G. 必须是独特的!

中文机器翻译题面 查看原题

配点 : 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

原案: 企鹅人