Стратегическая оборонная инициатива
“Командир! Командир! Проснись, командир!”
“... ммм. Который сейчас час?”
“4:07 утра, командир. Следующее сообщение только что пришло на аварийный шифратор, классифицированный как Zeta Priority.“
Вы нехотя берете письмо, стираете сон с глаз, на мгновение желая чтобы спонсор закрылся раньше, и начинаете читать.
Уважаемый командир SDI StarWars, Плохие новости, приятель. Сумасшедший Борис вчера вечером выпил немного водки, и когда он проснулся сегодня утром, вместо кнопки повтора на будильнике он ... ну, позвольте мне сказать так: сюда летят тонны ядерных ракет. К сожалению, все, что у нас есть, это диаграмма высот, на которой летят ракеты, а также порядок их прилета. Давай, приятель. Удачи. Министр обороны P.S. Хилли и Билл здороваются.
Что еще хуже, Вы помните что у SDI есть фатальный недостаток из-за сокращения бюджета. Когда SDI посылает ракеты для перехвата целей, каждая ракета должна лететь выше, чем предыдущая. Другими словами, как только вы попали в цель, следующая цель может быть только среди тех, которые летят на большей высоте, чем та, которую вы только что поразили.
Например, если ракеты летят на Вас на высоте 1, 6, 2, 3 и 5 (прибывают в указанном порядке), Вы можете попытаться перехватить первые две, но тогда Вы не сможете поймать те, которые летят на высотах 2, 3, 5, потому что они ниже 6. Ваша задача - поразить как можно больше целей. Таким образом, Вам следует написать программу, которая найдет лучшую последовательность целей, которую некорректная программа SDI собирается уничтожить.
Входные данные
Начинается со строки, содержащей количество тестов. За ней следует пустая строка. Пустая строка также расположена между двумя последовательными входными данными.
Каждый тест состоит из последовательности целых значений высоты, каждое в отдельной строке. Количество чисел в каждом тесте не более 10000.
Выходные данные
Для каждого теста выходные данные должны соответствовать формату приведенному в примере. Результаты двух последовательных наблюдений следует разделять пустой строкой.
Выходные данные должны содержать максимальное количество целей, которые Вы сможете поразить, с указанием высот этих целей, по одной в строке, в порядке их прибытия.