唐老师和猜数游戏

题目背景

唐老师支付了包装包裹的费用后，惊讶地发现他剩下的钱不够回家了！Walking Robot 提议道：“不如我们来玩个游戏吧，如果你赢了，我就用空间隧道把你传送回家。”金钱所剩无几的唐老师只好答应了它的提议。

题目描述

游戏规则如下：

1. Walking Robot 从 $1$ 到 $n$ 之间选择一个数字。
2. 唐老师来猜 Walking Robot 选了哪个数字。
3. 如果唐老师猜到正确的数字，就会赢得游戏。
4. 如果唐老师猜错了，那么 Walking Robot 会告诉他，它选的数字比他猜的更大或者更小，并且他需要继续猜数。
5. 每当唐老师猜了数字 $x$ 并且猜错了的时候，他需要支付金额为 $x$ 的现金。如果他花光了钱，就会输掉游戏 。

现在唐老师知道 $n$ 的大小，他想要知道确保他获胜的最小现金数，不管 Walking Robot 选择哪个数字。

输入格式

一行一个数字 $n$，表示 $n$ 的大小。

输出格式

一行一个数字，表示确保唐老师获胜的最小现金数。

样例 #1

样例输入 #1

10

样例输出 #1

16

样例 #2

样例输入 #2

1

样例输出 #2

0

样例 #3

样例输入 #3

2

样例输出 #3

1

提示

【数据范围】

共 $30$ 个数据点

对于前 $10$ 个数据点，$1 \leq n \leq 10$，每个数据点 $2$ 分

对于后 $20$ 个数据点，$1 \leq n \leq 200$，每个数据点 $4$ 分

【样例解释】

制胜策略如下：

• 数字范围是 $[1,10]$ 。唐老师先猜测数字为 $7$ 。
  • 如果这是 Walking Robot 选中的数字，他的总费用为 \ 0$。否则，他需要支付$$ 7$。
  • 如果 Walking Robot 的数字更大，则下一步需要猜测的数字范围是 $[8,10]$。唐老师可以猜测数字为 $9$。
    • 如果这是 Walking Robot 选中的数字，他的总费用为 \ 7$。否则，他需要支付$$ 9$。
    • 如果 Walking Robot 的数字更大，那么这个数字一定是 $10$。唐老师猜测数字为 $10$ 并赢得游戏，总费用为 \ 7 + $ 9 = $ 16$。
    • 如果 Walking Robot 的数字更小，那么这个数字一定是 $8$。唐老师猜测数字为 $8$ 并赢得游戏，总费用为 \ 7 + $ 9 = $ 16$。
  • 如果 Walking Robot 的数字更小，则下一步需要猜测的数字范围是 $[1,6]$。唐老师可以猜测数字为 $3$。
    • 如果这是 Walking Robot 选中的数字，他的总费用为 \ 7$。否则，他需要支付$$ 3$。
    • 如果 Walking Robot 的数字更大，则下一步需要猜测的数字范围是 $[4,6]$。唐老师可以猜测数字为 $5$。
      • 如果这是 Walking Robot 选中的数字，他的总费用为 \ 7 + $ 3 = $ 10$。否则，唐老师需要支付$$ 5$。
      • 如果 Walking Robot 的数字更大，那么这个数字一定是 $6$。唐老师猜测数字为 $6$ 并赢得游戏，总费用为 \ 7 + $ 3 + $ 5 = $ 15$。
      • 如果 Walking Robot 的数字更小，那么这个数字一定是 $4$。唐老师猜测数字为 $4$ 并赢得游戏，总费用为 \ 7 + $ 3 + $ 5 = $ 15$。
    • 如果 Walking Robot 的数字更小，则下一步需要猜测的数字范围是 $[1,2]$。唐老师可以猜测数字为 $1$。
      • 如果这是 Walking Robot 选中的数字，他的总费用为 \ 7 + $ 3 = $ 10$。否则，他需要支付$$ 1$。
      • 如果 Walking Robot 的数字更大，那么这个数字一定是 $2$。唐老师猜测数字为 $2$ 并赢得游戏，总费用为 \ 7 + $ 3 + $ 1 = $ 11$。

在最糟糕的情况下，唐老师需要支付 \ 16$。因此，他只需要$$ 16$ 就可以确保自己赢得游戏。