Задача 61. Поручение ≡

Условие

Сказали Волу:

— Уважаемый Вол!

Отвезите, пожалуйста,

В школу Стол.

— Ну, вот ещё,

Охота была!

Найдем

Какого-нибудь

Осла!

Осел подумал:

«Зачем мне мучиться?

Ведь в школах

Ослы

Не учатся.

Поручу-ка я это дело

Барану!»

...

Борис Заходер, "Муравей", 1961 г.

Звери ленятся и стараются перепоручить доставку другим зверям, поменьше размером. С другой стороны, искать кого-то поменьше им ещё больше лень, поэтому если рядом никого подходящего нет, то проще доставить самому.

По имеющемуся списку длины n размеров животных, определите размер наиболее длинной возможной цепочки "поручений". Доставку можно перепоручить следующему в списке или через одного (то есть следующему за следующим) если такие есть, но только в том случае, если его размер строго меньше.

Формат входных данных

Первая строка входного файла содержит натуральное число n — количество зверей. В следующей строке через пробел расположена перестановка натуральных чисел от 1 до n — их размеры.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

2 ≤ n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n = 2, получат не менее 10 баллов.

Решения, верно работающие при n = 3, получат не менее 10 баллов.

Пояснение к примеру

В примере дано десять зверей. Наиболее длинная цепочка поручений равна 3, она получается из чисел 9, 5 и 2 (или 9, 6 и 2).

Примеры тестов

10
10 1 4 9 5 6 2 8 3 7

3