Problem Description

At the cultural festival of JOI High School, lights are displayed in the hallway every year. The lights consist of $ N $ bulbs arranged in a single row from the west to the east side of the hallway. Each bulb is either on or off.

In the warehouse of JOI High School, there is a machine that can manipulate the bulbs. When this machine is used on a continuous sequence of bulbs, it toggles the state of all the bulbs in that sequence (i.e., it turns on all the bulbs that are off and turns off all the bulbs that are on). However, due to aging, the machine can only be used once.

The students of JOI High School like sequences where the bulbs alternate between being on and off (we call such sequences alternating sequences). Therefore, they decided to use the machine at most once to create a light display that includes as long an alternating sequence as possible.

Input Format

Read the following data from standard input:

• The first line contains an integer $ N $.
• The second line contains $ N $ integers separated by spaces, either $ 0 $ or $ 1 $. Each integer represents the state of a bulb before using the machine. The $ i $th integer ($1 \leq i \leq N$) represents the state of the $ i $th bulb from the west, where $ 1 $ means the bulb is on, and $ 0 $ means the bulb is off.

Output Format

Output a single line to standard output, containing an integer representing the maximum length of an alternating sequence that can be created in the bulb array by using the machine at most once.

Sample Input and Output

Sample Input #1

10
1 1 0 0 1 0 1 1 1 0

Sample Output #1

7

Sample Input #2

10
1 0 0 0 0 1 0 1 0 1

Sample Output #2

8

Sample Input #3

5
1 1 0 1 1

Sample Output #3

5

Sample Input #4

3
0 1 0

Sample Output #4

3

Notes/Hints

Example

For example, suppose the arrangement of the bulbs from west to east is:

○ ○ ● ● ○ ● ○ ○ ○ ●

(○ represents a bulb that is on, and ● represents a bulb that is off). If the machine is used on the bulbs from the 4th to the 7th, the arrangement becomes:

○ ○ ● ○ ● ○ ● ○ ○ ●

resulting in an alternating sequence of length 7 from the 2nd to the 8th bulb.

○ ○ ● ○ ● ○ ● ○ ○ ●

Alternatively, if the machine is used only on the 8th bulb, the arrangement becomes:

○ ○ ● ● ○ ● ○ ● ○ ●

resulting in an alternating sequence of length 7 from the 4th to the 10th bulb.

○ ○ ● ● ○ ● ○ ● ○ ●

It is not possible to create an alternating sequence of length 8 or more by using the machine at most once.

Task

Given the information about the light display, write a program to find the maximum length of an alternating sequence that can be obtained by using the machine at most once.

Constraints

$2 \leq N \leq 100,000$ - the number of bulbs in the light display.

Grading Criteria

For 20% of the scoring data, $N \leq 500$.

For 40% of the scoring data, $N \leq 2,000$.

见题面 Input 部分

见题面 Output 部分