Problem Description

On RedBlack Island, there are trees with a special property. These trees can turn red or black, and they have a unique characteristic. Multiple trees gather at one location and grow in a circle, forming a single row along the circumference of a certain circle.

Additionally, these trees have a property called "balancing" to prevent the same color from concentrating in one place. Specifically, if a tree and its two adjacent trees are all the same color, that tree will change to a different color the next day. More formally, let's say there are three trees $A, B, C$ arranged in this order, and their colors are $C_A, C_B, C_C$. If $C_A = C_B = C_C =$ red, then $C_B$ will turn black the next day. The same applies if they are all black.

However, these trees only look at their own situation on that day to balance, regardless of what their neighbors will do the next day. Therefore, it is possible for three consecutive trees of the same color to remain after one day (see the input example below). In such cases, they will continue to balance the next day.

As a researcher, you have observed the color situation of a group of $N$ trees on the first day. Determine on which day all the trees will stop changing color.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains the number of trees $N (3 ≦ N ≦ 10^5)$.
• The next $N$ lines contain the color information $color_i (color_i = 0, 1)$ for the $i$-th tree.
• If $color_i = 0$, the tree is black. If $color_i = 1$, the tree is red.
• The trees are arranged in a circular shape, so the $i$-th tree ($1 ≦ i ≦ N - 1$) is adjacent to the $(i + 1)$-th tree, and the $N$-th tree is adjacent to the $1$-st tree.

Output Format

Output the day on which all the trees stop changing color in one line. If such a day never comes, output $-1$.

Sample Input and Output

Sample Input #1

5
0
1
1
1
0

Sample Output #1

2

Sample Input #2

6
1
1
0
1
1
1

Sample Output #2

3

Sample Input #3

3
1
1
1

Sample Output #3

-1

Notes/Hints

Sample Explanation 1

Changes as shown in the figure below. No changes occur after the 2nd day. - On the 1st day, the 1st, 5th, and 6th trees change color because they and their neighbors are the same color. - On the 2nd day, the 6th tree changes color because it and its neighbors are the same color. - No changes occur after the 3rd day.

Sample Explanation 3

Alternates between all black and all red states.

见题面 Input 部分

见题面 Output 部分