Chisam's Paper Cutting

Time limit1sMemory limit1024 MB

Summary

Given N, find the fewest halving cuts needed to get at least N equal sheets when the pieces may come in at most two sizes.

Level: Medium5 of 10
Topics: Math, Bit manipulation, Greedy
Solved: No attempts yet

Problem

Chisam has one square sheet of paper. Chisam wants to get N sheets of the same size by cutting the paper exactly in half several times.

Chisam gets a headache when there are more than two kinds of paper sizes. So the cut pieces can come in at most two kinds of sizes.

The number on each sheet in the figure shows its size. Sheets with the same number are the same size. In the rightmost figure, Chisam has more than two kinds of sizes, so Chisam has a headache.

Each cut takes one piece. Pieces cannot be stacked or placed side by side to cut several at once.

Find the minimum number of cuts Chisam must make to get at least N sheets of the same size.

Input

The input is a single integer N, the number of sheets Chisam needs. N is a positive integer. ( $1 \le N < 2^{32}$ )

Output

Print the minimum number of cuts.

Examples1

Example 1
Input
```
13
```
Expected output
```
14
```