Иван-Царевич вышел на бой со Змеем Горынычем, у которого в начале сражения (\(t=0\) мин) было \(n\) голов. Василиса Премудрая предупредила Ивана, что Змей потеряет силу и будет повержен, только если у него останется ровно одна голова: ни больше, ни меньше.
У Ивана есть три приёма, каждый из которых занимает ровно 1 мин:
1) удар мечом — Змей теряет 1 голову;
2) удар булавой — Змей теряет 5 голов;
3) заклятие Василисы — у Змея остаётся только половина голов с округлением вниз (из \(x\) голов остаётся \(\displaystyle\left\lfloor \frac{x}{2} \right\rfloor\) голов).
За какое наименьшее время \(t_{\mathrm{min}}\) (в минутах) Иван-Царевич сможет одолеть Змея Горыныча? Приведите пример подходящей последовательности значений количества голов Змея в хронологическом порядке, начиная с момента \(t=0\) мин и заканчивая моментом \(t_{\mathrm{min}}\).
Формат входных данных
Программа получает на ввод единственное натуральное число \(n\). Гарантируется, что \(1\leqslant n\leqslant 10^5\).
Формат выходных данных
Программа должна вывести в первой строке единственное целое неотрицательное число — наименьшее время \(t_{\mathrm{min}}\) (в минутах), за которое Иван-Царевич сможет одолеть Змея Горыныча.
Затем во второй строке программа должна вывести через пробел элементы подходящей последовательности значений количества голов Змея в хронологическом порядке, начиная с момента \(t=0\) мин и заканчивая моментом \(t_{\mathrm{min}}\).
| № | Входные данные | Выходные данные |
|
1
|
1
|
0
1
|
|
2
|
3
|
1
3 1
|
|
3
|
14
|
3
14 7 6 1
|
|
4
|
1024
|
9
1024 512 256 128 64 32 27 13 6 1
|