Розворот послідовності
Фермер Джон вишикував 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.
Вихідні дані
Виведіть кількість елементів, які можуть утворити найбільшу зростаючу підпослідовність після реверсу вмісту не більше однієї підпослідовності.