Minimum Operations to One

Given an integer n with the constraint $2 \leq n \leq 10^9$, find the minimum number of operations needed to reduce it to 1. You can perform the following operations:

• If n is even, replace it with $\frac{n}{2}$.
• If n is odd, you can either replace it with n - 1 or n + 1.

For example, when n = 7, one optimal sequence is: 7 \(\to\) 8 \(\to\) 4 \(\to\) 2 \(\to\) 1, which requires 4 operations.

Your task is to implement an algorithm that minimizes the number of operations required to achieve 1. Note that for odd values, the decision whether to add or subtract 1 should be made optimally.

inputFormat

The input consists of a single integer n ($2 \leq n \leq 10^9$) given via standard input.

outputFormat

Output a single integer representing the minimum number of operations required to reduce n to 1. The output should be printed on standard output.

7

4