Problem

Given an integer, store its binary representation bin as a string or an array with digits indexed from 0 to length(bin)/2. Reduce its binary representation to zero by using the following operations:

1. Change the ith digit only if (i+1)th binary digit is 1 and all other digits from (i+2)to the end are zeros.
2. Change the rightmost digit without restriction.

Input

• long n: the starting value in base 10

Output

• int: the minimum number of operations required to covert n to 0

Constraints

• 1 <= n <= 10^15

Example

The binary representation of 4 is 100 so for the example, bin = [1, 0, 0].

Stepping through the operations:

• Use rule 2 to change bin(2) to 1. 100 -> 101
• Use rule 1 to change bin(1) to 1. 101 -> 111