問題文にミスがあったため、正しいものに差し替えました。「何日後に全ての木の色が…」→「何日目に全ての木の色が…」（22:00）

問題文

レッドブラックアイランドには特殊な性質を持った木が生えています。この木は赤色になったり黒色になったりする変わった木です。 この木には複数の個体が $1$ 箇所に集まって、ある円の円周上に $1$ 列に並ぶように生えるという特徴があります。

また、この木は同じ色が $1$ 箇所に集中しないように$1$日ごとに「バランスをとる」という性質があります。具体的には、自分とその両隣の木の色がすべて同じ色だったら、その木は次の日は異なる色に変わるという性質です。 より形式的に言うと、ある3つの木 $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

下図のように変化する。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

全部黒という状態と全部赤という状況を交互に繰り返す。