Суші для двох#10911

Суші для двох

1 секунда

128 мегабайтів

Легка

Аркадій запросив Ганну на вечерю в суші-ресторан. Ресторан трохи незвичайний: клієнту пропонується $n$ суші, викладених у ряд, і він повинен вибрати деякий підвідрізок із підряд розташованих суші.

Суші бувають двох видів: з тунцем або з вугром. Нехай $t_{i}$ t_i — тип $i$ -го суші зліва направо:

t_{i} = {1, якщо суші з тунцем, 2, якщо суші з вугром .

t_i = \begin{cases} 1, якщо~суші~з~тунцем,\\ 2, якщо~суші~з~вугром. \end{cases}

Аркадій не любить суші з тунцем, Ганна не любить суші з вугром. Аркадій хоче вибрати послідовний підвідрізок суші так, щоб:

У ньому було порівну суші обох типів.
Кожна половина підвідрізка містила тільки суші одного типу.

Наприклад:

Підвідрізок $[2, 2, 2, 1, 1, 1]$ [2, 2, 2, 1, 1, 1] підходить.
Підвідрізок $[1, 2, 1, 2, 1, 2]$ [1, 2, 1, 2, 1, 2] не підходить, тому що в обох половинах є суші обох типів.

Вхідні дані

Перша строка містить одне ціле число $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) — кількість суші.

Друга строка містить $n$ цілих чисел $t_{1}, t_{2}, \dots, t_{n} (t_{i} = 1$ t_1, t_2, \dots, t_n~(t_i = 1 або $t_{i} = 2)$ t_i = 2) — типи суші зліва направо.

Гарантується, що в наборі є принаймні одне суші кожного типу. Це означає, що існує принаймні один підходящий підвідрізок.

Вихідні дані

Виведіть одне ціле число — максимальну довжину підходящого підвідрізка.

Приклади

У першому прикладі Аркадій може вибрати підвідрізок $[2, 2, 1, 1]$ [2, 2, 1, 1] або підвідрізок $[1, 1, 2, 2]$ [1, 1, 2, 2], довжина яких $4$ .

У другому прикладі неможливо вибрати щось інше, окрім $[2, 1]$ або $[1, 2]$ , довжина яких $2$ .

У третьому прикладі найкращий вибір Аркадія — підвідрізок $[1, 1, 1, 2, 2, 2]$ [1, 1 ,1, 2, 2, 2].

Приклад 1

Приклад 2

Приклад 3