该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

分裂的函数

题目描述

定义函数 $f(x)$ 如下：

• 如果 $x = 1$，则 $f(x) = 0$
• 如果 $x > 1$，则 $f(x) = f(\lfloor x/2 \rfloor) + f(\lceil x/2 \rceil) + x$

其中

• $\lfloor \alpha \rfloor$ 表示令 $\alpha$ 向下取整
• $\lceil \alpha \rceil$ 表示令 $\alpha$ 向上取整

给定 $N$，请计算并输出 $f(N)$

输入格式

• 单个整数表示 $N$

数据范围

• 30% 的数据，$1 \le N \le 100$
• 60% 的数据，$1 \le N \le 1,000,000$
• 100% 的数据，$1 \le N \le 10^{17}$

样例数据

输入:

3

输出:

5