Учёные в одной секретной биологической лаборатории вывели новый уникальный вид бактерий, над размножением которых биологи имеют полный контроль.
В начальный момент времени (\(t=0\) сек) популяция бактерий состоит всего лишь из двух особей. Далее учёные собираются применить программу размножения бактерий, чтобы численность популяции в результате составляла ровно \(n\) особей. Программа размножения состоит из отдельных шагов, каждый из которых выполняется за 1 сек:
1) увеличить число бактерий в популяции на 1;
2) увеличить число бактерий в популяции на 10;
3) увеличить число бактерий в популяции в 2 раза.
За какое наименьшее время \(t_{\mathrm{min}}\) (в секундах) учёные смогут получить популяцию с требуемым количеством особей? Приведите пример подходящей последовательности значений количества особей в популяции в хронологическом порядке, начиная с момента \(t=0~\text{сек}\) и заканчивая моментом \(t_{\mathrm{min}}\).
Формат входных данных
Программа получает на ввод единственное натуральное число \(n\). Гарантируется, что \(2\leqslant n\leqslant 10^5\).
Формат выходных данных
Программа должна вывести в первой строке единственное целое неотрицательное число — наименьшее время \(t_{\mathrm{min}}\) (в секундах), за которое учёные смогут получить популяцию в \(n\) бактерий.
Затем во второй строке программа должна вывести через пробел элементы подходящей последовательности значений количества особей в популяции в хронологическом порядке, начиная с момента \(t=0~\text{сек}\) и заканчивая моментом \(t_{\mathrm{min}}\).
| № | Входные данные | Выходные данные |
|
1
|
2
|
0
2
|
|
2
|
6
|
2
2 3 6
|
|
3
|
15
|
3
2 4 5 15
|
|
4
|
1024
|
8
2 12 22 32 64 128 256 512 1024
|