分治除法

题目描述

黑板上写有一个整数 $N$。

高桥君将重复以下操作，直到黑板上所有不小于 $2$ 的整数都被移除：

• 选择黑板上一个不小于 $2$ 的整数 $x$。
• 擦掉黑板上一个 $x$，然后写上两个新整数 $\left\lfloor \dfrac{x}{2} \right\rfloor$ 和 $\left\lceil \dfrac{x}{2} \right\rceil$。

执行这一系列操作需要支付 $x$ 日元。

这里，$\lfloor a \rfloor$ 表示不超过 $a$ 的最大整数，$\lceil a \rceil$ 表示不小于 $a$ 的最小整数。

当无法再进行操作时，高桥君总共支付了多少钱？

可以证明，无论以何种顺序进行操作，支付的总金额都是确定的。

输入格式

输入按以下格式从标准输入给出：

$N$

输出格式

输出高桥君支付的总金额（日元）。

样例

3

5

以下是高桥君进行操作的一个示例：

初始时黑板上写有一个 $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$。

340

2888

100000000000000000

5655884811924144128

数据范围

• $2 \le N \le 10^{17}$