Назовём конечную последовательность натуральных чисел красивой, если она начинается с единицы и каждый её член, кроме первого, больше предыдущего на 1, на 7 или в 2 раза. Последовательность, состоящая из одной единицы, также является красивой.
Напишите программу, находящую наименьшую возможную длину красивой последовательности, заканчивающейся числом \(n\), а также приводящую пример такой последовательности наименьшей длины.
Формат входных данных
На вход программе подаётся единственное натуральное число \(n\). Гарантируется, что \(1\leqslant n\leqslant 10^5\).
Формат выходных данных
Программа должна вывести в первой строке единственное натуральное число — наименьшую возможную длину красивой последовательности, заканчивающейся числом \(n\).
Затем во второй строке программа должна вывести через пробел элементы красивой последовательности, являющейся примером, то есть имеющей выведенную выше длину и заканчивающейся числом \(n\).
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
1
|
|
2
|
2
|
2
1 2
|
|
3
|
9
|
3
1 2 9
|
|
4
|
128
|
6
1 8 16 32 64 128
|