Драконы символизируют мудрость, силу и богатство. На Китайский Новый год люди сооружают драконов из палок бамбука и ткани, поднимают их на палках, и перемещают палки вверх и вниз, чтобы изобразить летящего дракона.
Человек, держащий свой шест низко, может обозначаться как 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 называется длиной подпоследовательности.
Выходные данные
Выведите одно целое число — максимально возможную длину максимальной неубывающей подпоследовательности в получившейся последовательности.
Примечание
В первом примере после переворота подотрезка [2, 3] последовательность станет равна [1, 1, 2, 2], поэтому длина наибольшей неубывающей подпоследовательности равна 4.
Во втором примере после переворота подотрезка [3, 7] последовательность станет равна [1, 1, 1, 1, 2, 2, 2, 2, 2, 1], и длина наибольшей неубывающей подпоследовательности равна 9.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 1 2
|
4
|
|
2
|
10
1 1 2 2 2 1 1 2 2 1
|
9
|