Задача №111538. Микроконтроллеры
Михаил придумал решение задачи аппаратного кодирования видео с помощью последовательно соединенных микроконтроллеров. Каждый микроконтроллер выполняет определенную часть задачи, после чего передает данные следующему микроконтроллеру (получается некий конвейер из микроконтроллеров). В устройстве используется N микроконтроллеров, которые должны быть соединены последовательно: первый со вторым, второй с третьим и т. д. По задумке, микроконтроллеры располагались на плате в одну горизонтальную линию.
Михаил заказал платы с микроконтроллерами на фабрике, однако получилось так, что микроконтроллеры вместо того, чтобы стоять последовательно, оказались в хаотичном порядке! Поскольку заказ был довольно дорогим, Михаил решил максимально использовать имеющуюся плату, т.е. последовательно соединить дорожками наибольшее количество микроконтроллеров в цепочку вида 1 - 2 - ... - m. Оставшуюся часть придется заказать заново.
Плата, на которой расположены микроконтроллеры, будет односторонней (все дорожки расположены на одной плоскости и, естественно, не могут пересекаться). Если в микроконтроллер дорожка со входным сигналом входит сверху, то дорожка с выходным сигналом должна выходить из него обязательно снизу, и наоборот. Микроконтроллеры расположены вплотную друг к другу (проложить между ними дорожку нельзя). Обойти линию микроконтроллеров дорожкой слева или справа также нельзя (только сверху или снизу). Сверху и снизу от линии микроконтроллеров плата имеет достаточные размеры и позволяет проложить любое число дорожек.
Помогите Михаилу определить, какое максимальное количество последовательных микроконтроллеров удастся соединить, начиная с первого.
В первой строке входного файла задано число N — длина полоски из микроконтроллеров.
Во второй строке задана перестановка из N чисел — порядок расположения микроконтроллеров.
Выведите единственное число — максимальное количество микроконтроллеров, которые удастся соединить последовательно, начиная с первого.
Тесты состоят из четырех групп.
- Тест 1, из условия, оценивается в 0 баллов.
- В тестах этой группы количество микроконтроллеров N не превосходит 5 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы количество микроконтроллеров N не превосходит 100 000. Эта группа оценивается в 40 баллов, баллы начисляются только при прохождении всех тестов этой и предыдущей группы.
- В тестах этой группы количество микроконтроллеров N не превосходит 1 000 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов из всех групп.
7 5 1 4 7 6 3 2
5