分裂的函数

题目描述

定义函数 $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