Sushi for Two#10911
Arkady invited Anna to dinner at a sushi restaurant. The restaurant is a bit unusual: the customer is offered pieces of sushi arranged in a row, and must choose a contiguous subsegment of sushi.
Sushi comes in two types: with tuna or with eel. Let t_i denote the type of the -th sushi from left to right:
Arkady does not like sushi with tuna, and Anna does not like sushi with eel. Arkady wants to choose a contiguous subsegment of sushi such that:
It contains an equal number of sushi of both types.
Each half of the subsegment contains only sushi of one type.
For example:
Subsegment [2, 2, 2, 1, 1, 1] is valid.
Subsegment [1, 2, 1, 2, 1, 2] is not valid, because both halves contain sushi of both types.
The first line contains a single integer n~(2 \le n \le 10^5) — the number of sushi pieces.
The second line contains integers t_1, t_2, \dots, t_n~(t_i = 1 \text{ or } t_i = 2) — the types of sushi from left to right.
It is guaranteed that there is at least one sushi of each type in the set. This means there exists at least one valid subsegment.
Print a single integer — the maximum length of a valid subsegment.
In the first example, Arkady can choose the subsegment [2, 2, 1, 1] or [1, 1, 2, 2], both of length .
In the second example, nothing else can be chosen except or , both of length .
In the third example, Arkady's best choice is the subsegment [1, 1 ,1, 2, 2, 2].
Example 1
Example 2
Example 3