Black Chain

Time limit0.1sMemory limit512 MB

Summary

Given a chain of n rings (up to 10^18), find the fewest rings to open so the resulting pieces can be combined into every weight from 1 to n.

Level: Hard9 of 10
Topics: Greedy, Combinatorics, Number theory, Binary search
Solved: No attempts yet

Problem

There is a chain of n black rings linked in a row. Each black ring weighs exactly 1g. Using these rings, we want to produce every weight from 1g to ng. To do this, some rings must be opened, and since opening a ring takes effort, we want to open as few rings as possible. For example, suppose there is a black chain of 7 rings as in Figure A.1. If we open ring 3 in this chain, it splits into one ring (ring 3) and two chains (the chain of rings 1-2 and the chain of rings 4-7), as in Figure A.2. Using these, we can produce every weight from 1g to 7g, as in Figure A.3.

Figure A.1: A black chain of length 7

Figure A.2: A black chain split into 3 parts

Weight	1g	2g	3g	4g	5g	6g	7g
Ring composition	`[3]`	`[1-2]`	`[3]` `[1-2]`	`[4-7]`	`[3]` `[4-7]`	`[1-2]` `[4-7]`	`[3]` `[1-2]` `[4-7]`

Figure A.3: Ring compositions that produce every weight from 1g to 7g

Given a chain of n linked rings, write a program to find the minimum number of rings that must be opened to produce every weight from 1g to ng.

Input

Input is read from standard input. The first line gives the number of black rings n (3 ≤ n ≤ 1018).

Output

Output is written to standard output. Print the minimum number of rings that must be opened to produce every weight from 1g to ng.

Examples2

Example 1
Input
```
7
```
Expected output
```
1
```
Example 2
Input
```
20
```
Expected output
```
2
```