Problem Description

Every year, the school festival at JOI High School decorates the corridor with colored lights. The colored lights consist of $N$ bulbs, lined up in a row along the corridor from west to east. Each bulb is either on or off.

In the warehouse of JOI High School, there is a machine that can operate the bulbs. This machine can choose a consecutive segment of bulbs in the lights, then turn off all bulbs that are on within the chosen range, and turn on all bulbs that are off. However, because the machine is old, it can only be used once.

Students at JOI High School like sequences in which on and off bulbs alternate (such a bulb sequence is called an alternating sequence). Therefore, they decide to use this machine at most once if necessary, in order to create colored lights that contain an alternating sequence as long as possible.

For example, suppose the initial state of the colored lights from west to east is as follows ($\circ$ means a bulb is on, and $\bullet$ means a bulb is off):

:::align{center} :::

If we use the machine on the 4 bulbs from the 4th to the 7th, it becomes:

:::align{center} :::

Then, the bulbs from the 2nd to the 8th form an alternating sequence of length 7.

:::align{center} :::

Also, if we use the machine only on the 8th bulb, it becomes:

:::align{center} :::

Then, the bulbs from the 4th to the 10th form an alternating sequence of length 7.

:::align{center} :::

Even if we use the machine at most once, we cannot create an alternating sequence of length 8 or more.

Task

Given the information of the colored lights, write a program to find the maximum possible length of an alternating sequence contained in the bulb sequence, when the machine may be used at most once.

Input Format

Read the following data from standard input.

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

Output Format

Output one line to standard output containing an integer, which is the maximum length of an alternating sequence that can be contained in the resulting bulb sequence.

10
1 1 0 0 1 0 1 1 1 0

7

10
1 0 0 0 0 1 0 1 0 1

8

5
1 1 0 1 1

5

3
0 1 0

3

Hint

Sample Explanation

1. This is the example explained in the problem statement.
2. If we operate only the 4th bulb from the west, we can obtain an alternating sequence with the maximum value 8.
3. If we operate the bulbs from the 2nd to the 4th from the west, we can create an alternating sequence that includes all bulbs.
4. Note that sometimes it may not be necessary to use the machine.

Constraints

$2 \leq N \leq 100\,000$ The number of bulbs that make up the colored lights.

Scoring

In the testdata, the part worth 20% of the score satisfies $N \leq 500$.

In the testdata, the part worth 40% of the score satisfies $N \leq 2000$.

Translated by DeepSeek V3.2.

Translated by ChatGPT 5