该题作为 2025 年 4 月官方月赛 T1。

题目描述

在《我的世界》的方块世界里，有一排长长的格子状路径，总共有 $n$ 个方块位置。史蒂夫站在第 $1$ 个方块上，而他想要获取的珍贵宝物却在第 $n$ 个方块处。

史蒂夫可不想一步步辛苦地走过去，于是他从自己装满奇妙道具的背包里，拿出了一个红石门电路控制的机械傀儡。这个机械傀儡的移动遵循以下规则：

• 一开始，机械傀儡位于第 $1$ 个方块上。

• 如果机械傀儡当前在第 $x$ 个方块上，那么它可以选择跳到 $x - 1$、$x + 1$ 或者 $2 \cdot x$ 位置的方块上（但不能跳出这排方块路径的范围）。

这个机械傀儡最少需要跳跃多少次，才能顺利到达第 $n$ 个方块，帮史蒂夫拿到宝物呢？

输入格式

只有一行，一个正整数 $n$，代表这排方块路径的总方块数，同时也是宝物所在的方块位置。

输出格式

只有一行，一个正整数，表示机械傀儡到达宝物所在方块位置所需的最少跳跃次数。

输入输出样例

30

6

说明 / 提示

样例解释

1. $1 \to 2\quad(x+1)$
2. $2 \to 4\quad(2 \cdot x)$
3. $4 \to 8\quad(2 \cdot x)$
4. $8 \to 16\quad(2 \cdot x)$
5. $16 \to 15\quad(x-1)$
6. $15 \to 30\quad(2 \cdot x)$

共 $6$ 步。

数据范围与约定

对于 $100\%$ 的数据，$1 \le n \le 10^6$。