Mysterious Staircase Climb

After days of relentless work, the mathematicians of the Earth Defense Unit have finally deciphered the alien cipher. The message tells us that somewhere on Earth, in an ancient ruin, there lies a secret weapon to combat the impending catastrophe. The defense team rushes to the ruin only to find that entry is guarded by a mysterious staircase. In order to ascend it, you must follow its bizarre set of rules exactly:

1. If the height of the next step is exactly 1 unit higher than the current step, you may step up directly.
2. From every step except the first, you may take one step backward (i.e. to the immediately previous step).
3. If you take k consecutive backward moves, then in a single move you may jump upward to any step whose height is at most the current step's height plus \(2^{k}\). For example, if you are currently on the \(j\)th step and you reached there after a sequence of \(k\) backward moves, you are allowed to jump to any step with height at most \(\text{current height} + 2^{k}\). This upward jump, regardless of how many steps you skip, counts as a single move.

Initially you are on the first step. Time is of the essence and you need to reach the top of the staircase (step n) in as few moves as possible. Calculate the minimum number of moves required to ascend to the top.

inputFormat

The input consists of a single integer n (\(n \ge 1\)), representing the number of steps in the staircase. The steps are numbered from 1 to n and the height of a step is equal to its step number.

outputFormat

Output a single integer — the minimum number of moves required to reach the n-th step from the first step.

sample

3

2