103402: [Atcoder]ABC340 C - Divide and Divide

Problem Statement

There is a single integer $N$ written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than $2$ are removed from the blackboard:

• Choose one integer $x$ not less than $2$ written on the blackboard.
• Erase one occurrence of $x$ from the blackboard. Then, write two new integers $\left \lfloor \dfrac{x}{2} \right\rfloor$ and $\left\lceil \dfrac{x}{2} \right\rceil$ on the blackboard.
• Takahashi must pay $x$ yen to perform this series of operations.

Here, $\lfloor a \rfloor$ denotes the largest integer not greater than $a$, and $\lceil a \rceil$ denotes the smallest integer not less than $a$.

What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.

Constraints

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

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the total amount of money Takahashi will have paid, in yen.

Sample Input 1

3

Sample Output 1

5

Here is an example of how Takahashi performs the operations:

• Initially, there is one $3$ written on the blackboard.
• He chooses $3$. He pays $3$ yen, erases one $3$ from the blackboard, and writes $\left \lfloor \dfrac{3}{2} \right\rfloor = 1$ and $\left\lceil \dfrac{3}{2} \right\rceil = 2$ on the blackboard.
• There is one $2$ and one $1$ written on the blackboard.
• He chooses $2$. He pays $2$ yen, erases one $2$ from the blackboard, and writes $\left \lfloor \dfrac{2}{2} \right\rfloor = 1$ and $\left\lceil \dfrac{2}{2} \right\rceil = 1$ on the blackboard.
• There are three $1$s written on the blackboard.
• Since all integers not less than $2$ have been removed from the blackboard, the process is finished.

Takahashi has paid a total of $3 + 2 = 5$ yen for the entire process, so print $5$.

Sample Input 2

340

Sample Output 2

2888

Sample Input 3

100000000000000000

Sample Output 3

5655884811924144128

问题描述

黑板上写有一个整数$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$的最小整数。

当不能再执行操作时，高桥君将支付的总金额是多少？
可以证明，无论操作的顺序如何，他将支付的总金额是常数。

约束条件

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

输入

输入数据通过标准输入给出，格式如下：

$N$

输出

输出高桥君将支付的总金额，以日元为单位。

样例输入1

3

样例输出1

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。

样例输入2

340

样例输出2

2888

样例输入3

100000000000000000

样例输出3

5655884811924144128