← 返回题目列表

AtCoder · arc024_2

B. 红黑树

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

问题陈述中有一个错误,所以我用正确的陈述替换了它。 “多少天后所有的树都会被着色......”→“哪一天所有的树都会被着色......”(22:00)

問題文

红黑岛上生长着一棵具有特殊属性的树。这棵树是一棵不寻常的树,它会变红,有时会变黑。 这棵树有多个个体 1 聚集在一个地方并在某个圆的圆周上形成。 1 它的特点是成行生长。

另外,这棵树有相同的颜色。 1 避免集中于一处1每一天都有其自己的“平衡”性质。具体来说,如果你和你两边的树都是相同的颜色,那么第二天那棵树就会变成不同的颜色。 更正式地说,三棵树 A, B,C 按照这个顺序排列,每种颜色都是 假设 C_A, C_B, C_C 。此时 C_A = C_B = C_C = 如果是红色,则第二天 C_B 将为黑色。如果黑色和红色是相反的,也是如此。

然而,这棵树通过只考虑当天自己的情况来“平衡自己”,而不管第二天它的邻居会发生什么。因此 1 日复一日相同颜色的树 也可以将 3 连续两个(请参阅下面的输入示例)。那时,我第二天也会做同样的“平衡”。

作为一名研究人员,您 N 一群树。 1 我观察了当天的颜色情况。求出所有树木停止变色为止的天数。


入力

输入是按以下格式从标准输入给出的。

N
color_1
color_2
:
color_N
  • 1 行中树的数量 N (3 ≦ N ≦ 10^5) 。
  • 2 来自行 在 N 行 i 行是 i 第棵树颜色信息 color_i (color_i = 0, 1) 。
  • color_i = 0 ,树的颜色是黑色。 color_i = 1 ,树的颜色是红色。
  • 树木排列成圆形,所以 第 i(1 ≦ i ≦ N - 1) 棵树是 它位于 i + 1 树旁边, 它与第 N 棵树是 它位于 1 棵树相邻。

出力

多少天所有的树都会停止变色? 输出为 1 行。 如果那一天永远不会到来 -1 。


入力例1

5
0
1
1
1
0

出力例1

2

其变化如下所示。第二天后没有变化。

  • 1 日目、 3 树与其邻居树具有相同的颜色,因此第二天它会改变颜色。
  • 2 当天之后不会改变。

输入示例 2 中的图像有错误,所以我将其替换为正确的图像 (21:13)

入力例2

6
1
1
0
1
1
1

出力例2

3

其变化如下所示。 6 第棵树和 请注意,第 1 棵树是相邻的。

  • 1 日目、 1, 5, 6 树与其邻居树具有相同的颜色,因此第二天它会改变颜色。
  • 2 日目、 6 树与其邻居树具有相同的颜色,因此第二天它会改变颜色。
  • 3 当天之后不会改变。

入力例3

3
1
1
1

出力例3

-1

在全黑和全红之间交替。