题目描述

用二分算法从 $1$ 到 $N$ 中猜数字，你每次可以询问一个数字，裁判会告诉你"大了"还是"小了"。请你计算最坏情况下（即需要步数最多的那个数字）需要猜多少次才能保证猜对。

设要猜的数字为 $x$（$1 \le x \le N$），每次取中间值 $\text{mid} = \lfloor(1+N)/2\rfloor$，比较后调整范围，直到猜中。输出从 $1$ 到 $N$ 中所有数字猜中所需次数的最大值。

输入格式

一个整数 $N$，$1 \le N \le 10^9$。

输出格式

一个整数，表示最坏情况下需要的猜测次数。

样例

100

7

1000000000

30

说明/提示

对于全部测试数据，$1 \le N \le 10^9$。

提示：对于范围 $1\sim N$，最多需要 $\lceil \log_2 N \rceil$ 次即可找到。在代码中可以用二分模板模拟寻找最大步数：对每个可能的数字都跑一遍二分显然太慢，可以思考：哪个数字最"难找"？