Поповнення в сім'ї
Обмеження: 2 сек., 256 МіБ
Марічка й Зеник довго думали, зважували всі «за» і «проти». Було багато дискусій, суперечок, непорозумінь. Вони не були впевнені, чи готові до такої відповідальності. Але, здається, вони таки зважилися на цей поступок. У сім’ї нарешті буде поповнення!
У зоомагазині був дуже широкий вибір котиків — на всі смаки. Ніхто не міг залишитися байдужим. У молодят аж очі розбігалися від такого різноманіття. Марічка дуже хотіла обрати саме того єдиного, найкращого, найвеселішого, найдобрішого котика. Зеник же був просто щасливий, що в них удома нарешті появиться котик.
Процес відбору виявився доволі складним. Ключовим параметром для Марічки виявився параметр пухнастості котиків.
Усі nn котиків у зоомагазині вишикувалися в ряд. В ii-го котика рівень пухнастості рівний aiai. Процес відбору був багатоетапний. На кожному етапі Марічка забраковувала деяких котиків, і вони покидали конкурс. Решта переходили в наступний раунд, не міняючи свого відносного порядку.
Правила були такі: якщо безпосередньо справа від якогось котика стояв котик з більшим рівнем пухнастості, то на цьому етапі цей котик вважався малопухнастим. Наприкінці кожного етапу всі малопухнасті котики вибували з конкурсу. Зауважимо, що спочатку вибиралися малопухнасті котики, а тоді вже всі вони вибували з конкурсу.
У результаті всього цього процесу залишалася деяка послідовність котиків, таких що жодного з них Марічка не могла назвати малопухнастим. Одного із цих щасливців пара й забере до себе додому.
Ваше завдання — визначити результуючу послідовність не малопухнастих котиків.
Вхідні дані
У першому рядку задано ціле число nn — кількість котиків у зоомагазині.
У наступному рядку задано nn цілих чисел aiai — рівні пухнастості котиків у такому порядку, як вони вишикувалися.
Вихідні дані
У першому рядку виведіть ціле число mm — кількість котиків, що залишаться.
У другому рядку виведіть mm цілих чисел — рівні пухнастості котиків.
Обмеження
1≤ai≤1091≤ai≤109,
50%50% тестів: 1≤n≤10001≤n≤1000,
50%50% тестів: 1≤n≤1051≤n≤105,
гарантується, що у всіх котиків рівні пухнастості різні.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 7 6 5 7 2 3 1 4 | 2 7 4 |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 3 3 2 1 | 3 3 2 1 |
Примітки
Розберемо перший приклад.
На першому етапі малопухнастими будуть котики з пухнастостями 5, 2 й 1. Тому послідовність стане [6, 7, 3, 4]. На другому етапі малопухнастими будуть котики 6 і 3. Залишаться лише котики 7 і 4, кожен із яких не є малопухнастим.