Light Bulb Decoration

Interview

Time limit1sMemory limit128 MB

Summary

Given a binary string, flip at most one contiguous range so that some contiguous alternating substring becomes as long as possible, and report that length.

Level: Medium6 of 10
Topics: Array, Prefix sum, Implementation, Two pointers
Solved: No attempts yet

Problem

Every year during the festival, Sanggeun decorates the hallway with a colorful string of light bulbs. The decoration consists of $N$ bulbs arranged in a row, and each bulb is either on or off.

Sanggeun brought a machine that operates the bulbs. When you select one contiguous range of bulbs, the machine flips the state of every bulb in that range: bulbs that were on turn off, and bulbs that were off turn on. However, the machine is very old, so once it is used it cannot be used again until the next year.

The students like arrangements in which on and off bulbs appear alternately; such an arrangement is called an alternating pattern. Sanggeun wants to use the machine at most once to create the longest possible alternating pattern.

For example, suppose the bulbs are arranged as follows. (○ is an on bulb, ● is an off bulb.)

○ ○ ● ● ○ ● ○ ○ ○ ●

If the machine is used on the 4th through 7th bulbs (four bulbs), the result is:

○ ○ ● ○ ● ○ ● ○ ○ ●

Here the 2nd through 8th bulbs form an alternating pattern of length 7.

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

○ ○ ● ● ○ ● ○ ● ○ ●

In this case the 4th through 10th bulbs form an alternating pattern of length 7.

In this example, it is impossible to create an alternating pattern of length 8 or more with a single use of the machine.

Given the initial states of the bulbs, write a program that finds the length of the longest alternating pattern that can be obtained by using the machine at most once.

Input

The first line contains the number of bulbs $N$ . ( $2 \le N \le 100{,}000$ )

The second line contains the state of each bulb from left to right, separated by spaces. Each state is $1$ or $0$ , where $1$ means on and $0$ means off.

Output

Print the length of the longest alternating pattern that can be obtained by using the machine at most once.

Examples4

Example 1
Input
```
10
1 1 0 0 1 0 1 1 1 0
```
Expected output
```
7
```
Example 2
Input
```
10
1 0 0 0 0 1 0 1 0 1
```
Expected output
```
8
```
Example 3
Input
```
5
1 1 0 1 1
```
Expected output
```
5
```
Example 4
Input
```
3
0 1 0
```
Expected output
```
3
```