Descripción

Ser foráneo es un arte jajaja, van empezando las clases y como siempre llegas con la maleta llena de sueños, ideas y la alacena llena de... bueno, de lo único que te alcanzó por esta difícil cuesta de enero: Latas de Atún (tipo 1) y Sopas Maruchan (tipo 2).

Tienes todos tus víveres alineados en una fila en tu repisa. Como buen estudiante de Artes Visuales con TOC (Trastorno Obsesivo Compulsivo), quieres planear tu dieta para los próximos días siguiendo una regla estricta para "balancear" tu nutrición y no morir de gastritis ni de intoxicación por mercurio de esa sopa.

La regla de la "Dieta del Foráneo Equilibrada" es la siguiente:

1. Debes comer varios días seguidos de un solo tipo de alimento (ej. puro atún).
2. Inmediatamente después, debes comer exactamente la misma cantidad de días del OTRO tipo de alimento (ej. pura Maruchan).
3. Solo puedes tomar los alimentos en el orden en que están en la repisa (es una subcadena continua).

Por ejemplo:

• Si comes [Atún, Atún, Maruchan, Maruchan], es válido (2 días de cada uno).
• Si comes [Maruchan, Maruchan, Maruchan, Atún, Atún, Atún], es válido (3 días de cada uno).
• Si comes [Atún, Maruchan, Atún, Maruchan], NO es válido (porque alternas día a día, y tú necesitas rachas continuas por tipo).

¿Cuál es la mayor cantidad de días que puedes sobrevivir siguiendo esta dieta estricta con los víveres que tienes en la repisa?

Entrada

La primera línea contiene un número entero \(N (2 \le N \le 100,000)\) — el número total de alimentos en tu repisa. La segunda línea contiene \(N\) números enteros \(i_1, i_2, \dots, i_N\), donde cada número representa el tipo de alimento:

• 1: Lata de Atún.
• 2: Sopa Maruchan.

Se garantiza que hay al menos un atún y una Maruchan en la repisa.

Salida

Imprime un solo número entero: la longitud máxima de la dieta válida.

Ejemplos

Entrada

7
2 2 2 1 1 2 2

Salida

4

Entrada

6
1 2 1 2 1 2

Salida

2

Entrada

9
2 2 1 1 1 2 2 2 2

Salida

6

Nota

En el primer ejemplo (2 2 2 1 1 2 2), tienes 3 Maruchans seguidas, luego 2 Atunes, luego 2 Maruchans.

• Podrías elegir 2 2 1 1 (Dos Maruchans y luego Dos Atunes). Longitud = 4.
• No puedes elegir las 3 Maruchans iniciales porque solo tienes 2 Atunes para compensar después.

En el tercer ejemplo (2 2 1 1 1 2 2 2 2), tienes 2 Maruchans, luego 3 Atunes, luego 4 Maruchans.

• La mejor opción es tomar los 3 Atunes del medio y combinarlos con 3 de las 4 Maruchans que siguen al final: 1 1 1 2 2 2. Longitud = 6.