Поповнення в сім'ї
Limits: 2 sec., 256 MiB
Марічка й Зеник довго думали, зважували всі «за» і «проти». Було багато дискусій, суперечок, непорозумінь. Вони не були впевнені, чи готові до такої відповідальності. Але, здається, вони таки зважилися на цей поступок. У сім’ї нарешті буде поповнення!
У зоомагазині був дуже широкий вибір котиків — на всі смаки. Ніхто не міг залишитися байдужим. У молодят аж очі розбігалися від такого різноманіття. Марічка дуже хотіла обрати саме того єдиного, найкращого, найвеселішого, найдобрішого котика. Зеник же був просто щасливий, що в них удома нарешті появиться котик.
Процес відбору виявився доволі складним. Ключовим параметром для Марічки виявився параметр пухнастості котиків.
Усі \(n\) котиків у зоомагазині вишикувалися в ряд. В \(i\)-го котика рівень пухнастості рівний \(a_i\). Процес відбору був багатоетапний. На кожному етапі Марічка забраковувала деяких котиків, і вони покидали конкурс. Решта переходили в наступний раунд, не міняючи свого відносного порядку.
Правила були такі: якщо безпосередньо справа від якогось котика стояв котик з більшим рівнем пухнастості, то на цьому етапі цей котик вважався малопухнастим. Наприкінці кожного етапу всі малопухнасті котики вибували з конкурсу. Зауважимо, що спочатку вибиралися малопухнасті котики, а тоді вже всі вони вибували з конкурсу.
У результаті всього цього процесу залишалася деяка послідовність котиків, таких що жодного з них Марічка не могла назвати малопухнастим. Одного із цих щасливців пара й забере до себе додому.
Ваше завдання — визначити результуючу послідовність не малопухнастих котиків.
Input
У першому рядку задано ціле число \(n\) — кількість котиків у зоомагазині.
У наступному рядку задано \(n\) цілих чисел \(a_i\) — рівні пухнастості котиків у такому порядку, як вони вишикувалися.
Output
У першому рядку виведіть ціле число \(m\) — кількість котиків, що залишаться.
У другому рядку виведіть \(m\) цілих чисел — рівні пухнастості котиків.
Constraints
\(1 \le a_i \le 10^9\),
\(50\%\) тестів: \(1 \le n \le 1000\),
\(50\%\) тестів: \(1 \le n \le 10^5\),
гарантується, що у всіх котиків рівні пухнастості різні.
Samples
Input (stdin) | Output (stdout) |
---|---|
7 6 5 7 2 3 1 4 | 2 7 4 |
Input (stdin) | Output (stdout) |
---|---|
3 3 2 1 | 3 3 2 1 |
Notes
Розберемо перший приклад.
На першому етапі малопухнастими будуть котики з пухнастостями 5, 2 й 1. Тому послідовність стане [6, 7, 3, 4]. На другому етапі малопухнастими будуть котики 6 і 3. Залишаться лише котики 7 і 4, кожен із яких не є малопухнастим.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|