Problem Statement

レッドブラックアイランドには特殊な性質を持った木が生えています。この木は赤色になったり黒色になったりする変わった木です。 この木には複数の個体が $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$ 日目の色の状況を観測しました。何日目に全ての木の色が変わらなくなるか求めてください。

Input

入力は以下の形式で標準入力から与えられる。

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$ 番目の木と隣り合っている。

Output

すべての木の色が変わらなくなる日が何日目かを $1$ 行で出力せよ。 もし、そのような日が来ないのならば $-1$ を出力せよ。