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