Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

C. Извилистые движения
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Драконы символизируют мудрость, силу и богатство. На Китайский Новый год люди сооружают драконов из палок бамбука и ткани, поднимают их на палках, и перемещают палки вверх и вниз, чтобы изобразить летящего дракона.

Человек, держащий свой шест низко, может обозначаться как 1, а человек, держащий шест высоко — как 2. Таким образом ряд людей может быть представлен как последовательность a1, a2, ..., an, состоящая из единиц и двоек.

Маленький Томми тоже в этом ряду. Он хочет выбрать некоторый интервал [l, r] (1 ≤ l ≤ r ≤ n) и развернуть подотрезок al, al + 1, ..., ar так, чтобы длина наибольшей неубывающей подпоследовательности в получившейся последовательности была максимальной возможной.

Неубывающая подпоследовательность это такая последовательность индексов p1, p2, ..., pk, что p1 < p2 < ... < pk и ap1 ≤ ap2 ≤ ... ≤ apk. Число k называется длиной подпоследовательности.

Входные данные

Первая строка содержит одно целое число n (1 ≤ n ≤ 2000) — длину последовательности.

Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 2, i = 1, 2, ..., n) — исходная последовательность.

Выходные данные

Выведите одно целое число — максимально возможную длину максимальной неубывающей подпоследовательности в получившейся последовательности.

Примеры
Входные данные
4
1 2 1 2
Выходные данные
4
Входные данные
10
1 1 2 2 2 1 1 2 2 1
Выходные данные
9
Примечание

В первом примере после переворота подотрезка [2, 3] последовательность станет равна [1, 1, 2, 2], поэтому длина наибольшей неубывающей подпоследовательности равна 4.

Во втором примере после переворота подотрезка [3, 7] последовательность станет равна [1, 1, 1, 1, 2, 2, 2, 2, 2, 1], и длина наибольшей неубывающей подпоследовательности равна 9.