На день рождения ваш друг подарил вам n слизней, каждый из которых изначально имеет толщину 1.
Вы решили развлечься. Сначала вы ставите одного слизня на подоконник, а затем последовательно добавляете остальных. При добавлении очередного слизня вы ставите его правее всех уже имеющихся слизней. Пока на подоконнике находится больше одного слизня и крайние два справа имеют одну и ту же толщину v, вы можете объединить их вместе, чтобы создать слизня толщины v + 1.
Определите толщину всех слизней, которые будут стоять на подоконнике в конце этого процесса.
Выходные данные
Выведите единственную строку с k целыми числами, где k является итоговым количеством слизней после завершения процедуры, описанной в условии задачи. i-е из этих чисел должно быть толщиной i-го слева слизня.
Примечание
В первом примере у нас есть единственный слизень толщиной 1. Конечное состояние доски — 1.
Во втором примере мы выполняем следующие шаги:
- Размещаем на подоконнике одного слизня.
- Добавляем ещё одного слизня. Теперь подоконник выглядит как 1 1.
- Поскольку два последних слизня имеют одинаковую толщину, то мы заменяем этих слизней на одного слизня толщины 2.
Таким образом, конечное состояние подоконника равно 2.
В третьем примере после добавления первых двух слизней подоконник выглядит как 2. После добавления ещё одного слизня — 2 1.
В последнем примере шаги выглядят следующим образом:
- 1
- 2
- 2 1
- 3
- 3 1
- 3 2
- 3 2 1
- 4
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
|
|
2
|
2
|
2
|
|
3
|
3
|
2 1
|
|
4
|
8
|
4
|