465. 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 when 'R' is executed. 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 when 'R' is executed. 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 required to reach the target position.

Example

Input

6

Output

5

Constraints

1 <= target <= 10^4

Loading...

View Submissions

Console