eolymp
bolt
Try our new interface for solving problems
Problems

Am I Drunk?

Am I Drunk?

Time limit 1 second
Memory limit 64 MiB

After drinking more than 10^12 “rumka”s in Rashad’s wedding ceremony, Murad and Barish both can’t differ 2 from 3. However,they still challenge themselves! Murad has a lot of coins, and he put them on the table in some order (he is drunk as hell, so he doesn’t know why exactly this order!). These coins can be expressed as 0 or 1, where 0 means head and 1 means tail. Now, he knows that Barish doesn’t like alternating sequences, so he will ask him to find maximum length of contiguous alternating 0 and 1 sequence (that is,like 0101 or 101 and so on). But Murad wants to make counting difficult for Barish, so he will choose at most one contiguous subarray and flip the all coins (that is, 0 becomes 1 and vice versa) to get maximum length of alternating contiguous subarray! While Barish is trying to revitalize himself, you need to help Murad to make that decision wisely and get the maximum length of alternating contiguous subarray.

Input data

The number N (1N10^5 ) is given in the first line. The next line contains N numbers, each being 0 or 1.

Output format:

The maximum length of the explained subarray after flipping numbers in at most one subarray.

Explanation for test cases

First Test Case:

If you make the operation at the indices from 4 to 7, then the array becomes: 1 1 0 1 0 1 0 1 1 0 .Red part is alternating and has length 7 .

Second Test Case:

Only change the 4-th index1 0 0 1 0 1 0 1 0 1

Examples

Input example #1
10
1 1 0 0 1 0 1 1 1 0
Output example #1
7
Input example #2
10
1 0 0 0 0 1 0 1 0 1
Output example #2
8
Source IZHO 2019-2020 Azerbaijan selection contest