Jump Hide-and-Seek

Time limit1sMemory limit512 MB

Summary

Starting at 0, each jump doubles the previous one (1, 2, 4, ...); find the minimum number of jumps to land exactly on K, or report -1.

Level: Medium6 of 10
Topics: Math, Greedy, Bit manipulation, Brute force
Solved: No attempts yet

Problem

Hyunwook is playing hide-and-seek with his older brother. Hyunwook is currently at point $0$ , and his brother is at point $K$ ( $-10^{12} \le K \le 10^{12}$ ).

Hyunwook likes jumping, so he always moves by jumping. His first jump covers a distance of $1$ . He gets more excited with each jump, so every jump covers twice the distance of the previous jump.

Given the position of Hyunwook's brother, find the minimum number of jumps Hyunwook needs to reach him.

Input

The first line gives the position $K$ of Hyunwook's brother ( $-10^{12} \le K \le 10^{12}$ ).

Output

On the first line, print the minimum number of jumps Hyunwook needs to reach his brother's position. If there is no way to reach it, print $-1$ .

Examples3

Example 1
Input
```
3
```
Expected output
```
2
```
Example 2
Input
```
-7
```
Expected output
```
3
```
Example 3
Input
```
2
```
Expected output
```
-1
```