分数: 300 点
问题陈述
有一个整数 N 写在黑板上。
Takahashi会重复以下一系列操作,直到所有不小于的整数 2 从黑板上删除:
- 选择一个整数 黑板上写着 x 不小于 2 。
- 删除 1 个出现的 黑板上的 x 。然后,写入两个新整数 黑板上的 \left \lfloor \dfrac{x}{2} \right\rfloor 和 \left\lceil \dfrac{x}{2} \right\rceil 。
- 高桥必须支付 x 日元执行这一系列操作。
在这里, \lfloor a \rfloor 表示不大于的最大整数 a,和 \lceil a \rceil 表示不小于的最小整数 a.
当无法进行更多操作时,高桥将支付的总金额是多少?
可以证明,无论操作执行的顺序如何,他将支付的总金额都是恒定的。
约束
- 2 \leq N \leq 10^{17}
输入
输入由标准输入按以下格式给出:
N
输出
打印高桥将支付的总金额(以日元为单位)。
示例输入 1
3
示例输出 1
5
以下是 Takahashi 如何执行操作的示例:
- 最初,有一个 3 。
- 他选择 3。他付钱 3 日元,删除一个 3 从黑板上写下 \left \lfloor \dfrac{3}{2} \right\rfloor = 1 和 \left\lceil \dfrac{3}{2} \right\rceil = 2 。
- 有一个 2 和一个 1 。
- 他选择 2。他付钱 2 日元,删除一个 2 从黑板上写下 \left \lfloor \dfrac{2}{2} \right\rfloor = 1 和 \left\lceil \dfrac{2}{2} \right\rceil = 1 。
- 共有三个 黑板上写着 1。
- 由于所有整数不小于 2 已从黑板上移除,该过程已完成。
高桥已支付总计 3 + 2 = 5 日元整个过程,所以打印 5.
示例输入 2
340
示例输出 2
2888
示例输入 3
100000000000000000
示例输出 3
5655884811924144128