问题描述

Red Black Island 上生长着一种具有特殊性质的树木。这些树木可以变成红色或黑色，非常奇特。这些树木集中在一个地方，以直线排列在一个圆的周长上。

此外，这些树木有一个称为“平衡”的特性，即它们每天都会“平衡”，以防止相同颜色的树木集中在一起。具体而言，如果一个位置的三棵树木A、B和C依次排列，并且它们的颜色分别是C_A、C_B和C_C，那么如果C_A = C_B = C_C = 红色，则第二天C_B会变成黑色。如果颜色是黑色和红色的相反情况，也是同样处理。

然而，这些树木只根据它们当天的状态来“平衡”，而不考虑邻近的树木将如何变化。因此，在一天过去后，仍然可能有连续3棵相同颜色的树木（请参考下面的示例）。在这种情况下，它们第二天也会继续“平衡”。

作为研究者，你观察到了一个由N棵树木组成的群体的第一天的颜色情况。请计算多少天后所有树木的颜色将不再改变。

输入

输入从标准输入中读取，具有以下格式。

$N$ $color_1$ $color_2$ : $color_N$

• 第一行为树木的数量$N(3≤N≤10^5)$。
• 接下来的$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

5
0
1
1
1
0

输出示例1

2

树木的变化如下图所示。从第2天开始，它们的颜色不再改变。

• 第1天，第3棵树的颜色与邻近的树木相同，所以下一天它们的颜色会改变。
• 从第2天开始，树木的颜色不再改变。

示例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

交替出现所有黑色和所有红色的情况。