You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在神秘秀丽的云南大理，崇圣寺三塔矗立在苍山洱海之间，见证了南诏古国的兴衰。相传南诏国王得到了一对世间罕见的“金翅鸟蛋”，坚硬无比。国王想知道这神蛋究竟坚硬到何种程度，于是召集天下智者，来到高达 $N$ 层的千寻塔（主塔）进行测试。 为了不浪费这稀世珍宝，国王规定：只能使用这两颗金翅鸟蛋。测试的目标是找出这颗蛋从多高的楼层扔下恰好不会碎（即：从该层及以下扔下不碎，从该层上一层扔下就会碎）。

题目描述

千寻塔共有 $N$ 层（层数从 $1$ 到 $N$ 编号）。你有两颗完全一样的金翅鸟蛋。 已知存在一个临界楼层 $F$ ($0 \le F \le N$)，满足：

如果从第 $L$ 层扔下鸡蛋，且 $L \le F$，鸡蛋不会碎。 如果从第 $L$ 层扔下鸡蛋，且 $L > F$，鸡蛋一定会碎。 特别地，如果 $F=0$，表示从第 1 层扔下也会碎；如果 $F=N$，表示从第 $N$ 层扔下也不会碎。

你的任务是制定一个测试策略，使得在最坏情况下（即 $F$ 取值最刁钻时），扔鸡蛋的总次数最小。请计算这个最小的扔鸡蛋次数。 注意：

如果鸡蛋没碎，可以捡回来继续使用。 如果鸡蛋碎了，就不能再使用了。 你只有两颗鸡蛋，如果两颗都碎了，测试就必须停止（此时你必须已经确定了 $F$ 的值）。

输入格式

输入一行，包含一个正整数 $N$，表示千寻塔的总层数。

输出格式

输出一行，包含一个整数，表示在最坏情况下，确定临界楼层 $F$ 所需的最小扔鸡蛋次数。

样例输入 1

100

样例输出 1

14

样例输入 2

10

样例输出 2

4

数据范围与提示

对于 30% 的数据，$N \le 100$。 对于 60% 的数据，$N \le 10^5$。 对于 100% 的数据，$1 \le N \le 10^{18}$。

提示： 本题不仅仅是数学计算，更考验策略。 假设你计划在 $k$ 次内测出结果。 第一次，你应该在哪一层扔第一颗鸡蛋？

如果碎了，你只剩下一颗鸡蛋，为了确定 $F$，你必须从第 1 层开始逐层向上试，最多能试多少层？ 如果没碎，你还剩两颗鸡蛋，但你已经用掉了一次机会，剩下 $k-1$ 次机会，接下来应该去哪一层？

请仔细思考层数与次数之间的关系。