Min Operations to One

You are given a positive integer n. Your task is to determine the minimum number of operations required to reduce n to 1. At each step, you may perform one of the following operations:

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

The goal is to achieve this with the minimum number of operations.

Note: When applying the odd operations, a common strategy is to subtract 1 if \(n = 3\) or if reducing \(n\) leads to a number that is more divisible by 2; otherwise, add 1. Formally, if \(n\) is odd and \(n \neq 1\), choose the operation in such a way that it minimizes the total operations to reach 1.

You are expected to read the input from standard input (stdin) and print the answer to standard output (stdout).

inputFormat

The input consists of a single line containing the integer \(n\) (where \(1 \leq n \leq 10^{18}\)).

outputFormat

Output a single integer: the minimum number of operations required to transform \(n\) into 1.

## sample

8

3

</p>