Minimizing AzureHair's Dilemma

AzureHair has been locked in a room with n cats. Every day, he is required to hand over exactly \( \frac{n}{2} \) of the cats if n is even. However, if n is odd, he faces a dilemma: he can either give \( \frac{n+1}{2} \) cats or \( \frac{n-1}{2} \) cats away. Each time he encounters an odd number \( n \) and must make this choice, it counts as one instance of dilemma.

Your task is to compute the minimum number of dilemmas AzureHair will encounter until all cats have been removed from the room. The process is carried out day by day, where on each day the number of cats handed over is determined by the current number of cats remaining. The process ends when there are no cats left.

The recurrence can be formulated as follows:

[ f(n) = \begin{cases} 0, & n = 0,\ 1, & n = 1,\ f(\frac{n}{2}), & n \text{ is even and } n > 0,\ 1 + \min\left(f\Big(\frac{n-1}{2}\Big), f\Big(\frac{n+1}{2}\Big)\right), & n \text{ is odd and } n > 1. \end{cases} ]

inputFormat

The input consists of a single integer n (\(0 \leq n \leq 10^6\)), representing the total number of cats.

outputFormat

Output a single integer, which is the minimum number of dilemmas AzureHair will have to face until all cats are removed.

sample

1

1