#P1000. 小景爱跑步

小景爱跑步

小景爱跑步

  小景曾经是国家级跳远健将,但是他重生了,重生成为了一个跑步爱好者。
  今天又是阳光明媚的一天啊,我们的小景开始了他一天的跑步时光,他初始位置为1 ,他今天准备到第n公里,也就是跑n - 1的距离,已知小景的初速度为1m/s,但是小景觉得他的速度太慢了,于是他准备用他前世的跳跃能力来帮他完成这个路程。
  当小景位于x处时,他有两个选择:
  1.按照正常速度跑步。
  2.开始蓄力,i秒钟可以蓄2i2^i的距离。例如:小景在x处,蓄力两秒,他可以跳跃到x+222^2 的位置。注意:跳跃也需要1秒的时间。

Input

输入仅包含一个整数 n( 1 <= n <= 200000),表示终点位置。

Output

一个整数,表示最少花费的时间。

Samples

1
0
5
3