题目描述

地上有一排格子，共 $n$ 个位置。小达站在第一个格子上，需要取第 $n$ 个格子里的东西。

小达当然不愿意自己跑过去，所以小达从口袋里掏出了一个奇怪的机器人！这个机器人的行动遵循下面的规则：

• 初始时，机器人位于 $1$ 号格子
• 若机器人目前在 $x$ 格子，那么它可以跳跃到 $x+1, x-1, 2x$ 里的一个格子（不允许跳出界）

问机器人最少需要多少次跳跃，才能到达 $n$ 号格子。

输入格式

仅一行，一个正整数，表示 $n$。

输出格式

输出两行。

第一行包含一个正整数，表示最少跳跃次数。

第二行是机器人从第 $1$ 个格子跳到第 $n$ 个格子的最短路径（当存在多个最短路径时，优先考虑 $x + 1$，再考虑 $x - 1$，最后考虑 $2x$，即机器人在行动时会按这个顺序来跳跃）。

样例

64

6
1 2 4 8 16 32 64

63

8
1 2 4 8 16 32 31 62 63

样例解释

第二组数据的 $63$ 不能通过 $64-1$ 得到，因为格子总数为 $63$，没有第 $64$ 个格子。

数据范围

对于 $100\%$ 的数据，有 $1\leq n \leq 1000000$。