Разворот последовательности
Фермер Джон выстроил n своих коров в ряд, чтобы сделать фото. Высота i-ой коровы в этом ряду есть a(i), и ФД думает, фото будет эстетически приятным, если будет иметь большую возрастающую по росту коров подпоследовательность.
Напомним, подпоследовательность это подмножество a(i[1]), a(i[2]), .. , a(i[k]) элементов из последовательности, где индексы i[1] < i[2] < ... < i[k]. Мы говорим, что подпоследовательность возрастающая, если a(i[1]) ≤ a(i[2]) ≤ ... ≤ 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 (1 ≤ n ≤ 50). Остальные n строк содержат a(1) .. a(n), целые числа в интервале 1 .. 50.
Выходные данные
Выведите количество элементов, которые смогут сформировать наибольшую возрастающую подпоследовательность после реверса содержания не более одной подпоследовательности.