Minimum Number of Jumps

Doraemon's robot needs to move from the first cell to the \(n\)th cell along a row of \(n\) cells. The robot can move according to the following rules:

• If the robot is at cell \(x\), it can jump to cell \(x-1\), \(x+1\), or \(2x\) (provided the destination is within the range of \(1\) to \(n\)).

Determine the minimum number of jumps required for the robot to reach cell \(n\).

inputFormat

The input consists of a single integer \(n\) \((1 \leq n \leq 10^5)\) representing the number of cells.

outputFormat

Output a single integer representing the minimum number of jumps needed for the robot to reach cell \(n\).

sample

1

0