Задача №111547. Неудачная покупка

Олимпиада завершена. Режим дорешивания.

Иннокентий придумал решение задачи аппаратного кодирования видео с помощью последовательно соединенных микроконтроллеров. Каждый микроконтроллер выполняет определенную часть задачи, после чего передает данные следующему микроконтроллеру (получается некий конвейер из микроконтроллеров). В устройстве используется N микроконтроллеров, которые должны быть соединены последовательно: первый со вторым, второй с третьим и т.д. По задумке, микроконтроллеры располагались на плате в одну горизонтальную линию.

Иннокентий заказал платы с микроконтроллерами на фабрике, однако получилось так, что микроконтроллеры вместо того, чтобы стоять последовательно, оказались в хаотичном порядке! Поскольку заказ был довольно дорогим, Иннокентий решил максимально использовать имеющуюся плату, т.е. последовательно соединить дорожками наибольшее количество микроконтроллеров в цепочку вида 1 — 2 — ... — M. Оставшуюся часть придется заказать заново.

Плата, на которой расположены микроконтроллеры, будет односторонней (все дорожки расположены на одной плоскости и, естественно, не могут пересекаться). Если в микроконтроллер дорожка со входным сигналом входит сверху, то дорожка с выходным сигналом должна выходить из него обязательно снизу, и наоборот. Микроконтроллеры расположены вплотную друг к другу (проложить между ними дорожку нельзя). Обойти линию микроконтроллеров дорожкой слева или справа также нельзя (только сверху или снизу). Сверху и снизу от линии микроконтроллеров плата имеет достаточные размеры и позволяет проложить любое число дорожек. Помогите Иннокентию определить, какое максимальное количество последовательных микроконтроллеров удастся соединить, начиная с первого.

Входные данные

В первой строке входного файла задано число N, 0≤=N≤=100. Во второй строке задана перестановка из N чисел микроконтроллеров.

Выходные данные

Выведите единственное число — максимальное количество микроконтроллеров, которые удастся соединить последовательно, начиная с первого.

Примечание

Вспомогательный рисунок по тесту из условия. Перейдите по ссылке (скопируйте в адресную строку): http://cs410924.userapi.com/v410924841/693e/qs7jQmmnScw.jpg

Примеры
Входные данные
7
5 1 4 7 6 3 2
Выходные данные
5
Сдать: для сдачи задач необходимо войти в систему