858. Follow Instructions

0

Hard

Sumit is driving his car on an infinite number line. The car starts at position 0 and has a speed of +1. The car can move in both positive and negative directions. Sumit can control the car by giving it a sequence of instructions, which can be either 'A' (accelerate) or 'R' (reverse):

For 'A' : Accelerate

Actions Taken :

-> position += speed

-> speed *=2 For 'R'

Actions Taken :

If speed > 0, then speed = -1,

Otherwise, speed = 1. The position of the car remains the same after reversing. Given a target position, you need to determine the length of the shortest sequence of instructions required to reach that target.

For 'A' : Accelerate

Actions Taken :

-> position += speed

-> speed *=2 For 'R'

Actions Taken :

If speed > 0, then speed = -1,

Otherwise, speed = 1. The position of the car remains the same after reversing. Given a target position, you need to determine the length of the shortest sequence of instructions required to reach that target.

Input Format

The target position as an integer.

Output Format

The length of the shortest sequence of instructions as an integer.

Example

Input

6

Output

5

Constraints

1 <= target <= 10^4

Loading...

View Submissions

Console