题目描述

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

输出格式

3

5

数据范围

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

来源

改编自 ABC340C Divide and Divide