Фермер Джон выстроил \(N\) своих коров в ряд, чтобы сделать фото
(\(1 \leq N \leq 50\)). Высота \(i\)-ой коровы в этом ряду есть \(a(i)\), и
ФД думает, фото будет эстетически приятным, если будет иметь большую
возрастающую по росту коров подпоследовательность.
Напомним, подпоследовательность это подмножество \(a(i_1), a(i_2), \ldots, a(i_k)\)
элементов из последовательности, где индексы \(i_1 < i_2 < \ldots < i_k\).
Мы говорим, что подпоследовательность возрастающая, если
\(a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)\).
ФД может переупорядочивать коров следующим образом
выбрать любую подпоследжовательность и реверсировать её элементы
Например, если мы имееем список
1 6 2 3 4 3 5 3 4
мы можем реверсировать следующие элементы
1 6 2 3 4 3 5 3 4
^ ^ ^ ^
получим
1 4 2 3 4 3 3 5 6
^ ^ ^ ^
Заметим, что элементы располагаются на тех же индексах, где они
были изначально, оставляя нетронутыми другие элементы.
Определите максимально возможную длину возрастающей подпоследовательности
основываясь на факте, что Вы можете реверсировать любую подпоследовательность,
но только один раз.
Формат входных данных:
Первая строка ввода содержит числа \(N\). Остальные \(N\) строк содержат
\(a(1) \ldots a(N)\), целые числа в интервале \(1 \ldots 50\).
ФОРМАТ ВЫВОДА (файл subrev.out):
Выведите количество элементов, которые смогут сформировать наибольшую
возрастающую подпоследовательность после реверса содержания
не более одной подпоследовательности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
1
2
3
9
5
6
8
7
4
|
9
|