13448: 跳跃机器人

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:15 Solved:11

Description

地上有一排格子,共  个位置,编号分别为 1 。机器猫站在第一个格子上,需要取第  个格子里的东西。

机器猫当然不愿意自己跑过去,所以机器猫从口袋里掏出了一个机器人!这个机器人的行动遵循下面的规则:

  • 初始时,机器人位于 1 号格子
  • 若机器人目前在  格子,那么它可以跳跃到 1,+1,2 里的一个格子(不允许跳出界)

问机器人最少需要多少次跳跃,才能到达  号格子。

Input

仅一行,一个正整数,表示 

Output

仅一行,一个正整数,表示最少跳跃次数。

Sample Input Copy

30

Sample Output Copy

6

HINT

样例解释:

1248161530

数据规模与约定

对于 100% 的数据,有 11000000