题目背景

Special for beginners, ^_^

题目描述

在远古王国里，有一块古老的魔法石。

魔法石的能量规则如下：

当 n=1 时，能量值为 1

当 n>1 时，魔法石会分裂成两块：

一块大小为 ⌊n/2⌋

一块大小为 ⌈n/2⌉

总能量 = 左半部分能量 + 右半部分能量 + n

现在给你一个整数 n，请你用递归的方法求魔法石的总能量。

输入格式

一个整数 n，满足 $1\le n\le 10^6$。

输出格式

输出一个整数，表示总能量。

样例

4

12

样例解释

f(4)=f(2)+f(2)+4 f(2)=f(1)+f(1)+2=1+1+2=4

所以： f(4)=4+4+4=12