Radiation Detection

Program time limit: 1 second

Program memory limit: 512 MB

You find yourself suddenly in a 1-dimentional radioactive wasteland! You realise that you need to figure out which pieces of land are safe and which are not. In this 1-dimentional world, there are $n$ pieces of land consecutively labelled by their coordinate starting at $1$.

If the bomb exploded at position $k$, every land that has a position greater than $k$ is polluted. You have 2 detectors that can detect if a land is polluted, however, if you use your detector over a piece of polluted land, that detector breaks.

You hate walking, so you want to figure out the minium number of detections you need to make to be sure of the value of $k$.

Note: there could be no polluted land, in that case $k$ would be $n$.

Input

The first and only line of input contains an integer $n$

Constraints

For all test cases:

• $1 \le n \le 1\;000\;000\;000$.

Output

Output a single integer: the minimium number of detections that needed to be made.

Sample Input 1

2

Sample Output 1

2

Explanation 1

We need to check both pieces of land to see where the bomb is. e.g., if we check land $1$ and it isn't radio active we also need to check land $2$.

Sample Input 2

5

Sample Output 2

3

Explanation 2

You can first detect land $3$, if it breaks, then we know k is $1$, $2$, or $3$, so it is sufficient to test both $1$ and $2$. If land $3$ doesn't break, we know $k$ is larger, so it is sufficient to test land $4$ and $5$.

Scoring

Your program will be run on the 2 sample cases and multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves the task. Recall that your final score on the task is the score of your highest scoring submission.

Submit

Past submissions

You haven't submitted to this task.