Розворот послідовності#10555

Розворот послідовності

1 секунда

128 мегабайтів

Дуже складна

Фермер Джон вишиковує своїх $n$ корів у ряд, щоб сфотографувати їх. Зріст $i$ -ї корови в цьому ряду дорівнює $a_{i}$ a_i, і Фермер Джон вважає, що фотографія виглядала б естетичніше, якби в ряду була довга зростаюча підпослідовність корів за зростом.

Нагадаємо, що підпослідовність — це послідовність елементів $a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{k}}$ a_{i_1}, a_{i_2}, \ldots, a_{i_k} вихідної послідовності, відповідні індекси яких задовольняють умові $i_{1} < i_{2} < \dots < i_{k}$ i_1 < i_2 < \ldots < i_k. Ми називаємо підпослідовність зростаючою, якщо $a_{i_{1}} \leq a_{i_{2}} \leq \dots \leq a_{i_{k}}$ a_{i_1} \le a_{i_2} \le \ldots \le 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 \leq n \leq 50)$ n~(1 \le n \le 50). У наступних $n$ рядках містяться $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n, де кожне $a_{i}$ a_i є цілим числом у діапазоні $1 \dots 50$ .

Вихідні дані

Виведіть максимально можливу довжину зростаючої підпослідовності після зміни на протилежний порядок елементів не більше ніж однієї підпослідовності.

Приклади

Приклад 1