You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

细胞并不是可以无限分裂下去

端粒

题目描述

在细胞内, 有一个长度为 $n$ 的端粒, 细胞每分裂一次, 端粒的长度就会减少一段.

对于一个细胞的分裂, 假如它的端粒长度为 $x$

如果端粒长度为 $1$, 无法进行分裂, 细胞会消亡

如果端粒长度 $\ge 1$, 细胞将会分裂为 $2$ 个, 端粒变为 $\lfloor \dfrac{x}{2} \rfloor$

我们想知道, 在足够长的时间内, $1$ 个端粒长度为 $n$ 的细胞及其它的分裂细胞个数一共是多少.

输入格式

给你一个整数 $n$ 表示初始细胞的端粒长度

样例 #1

样例输入 #1

2

样例输出 #1

3

样例 #2

样例输入 #2

4

样例输出 #2

7

样例解释

长度为 $4$ 的细胞分裂出 $2$ 个长度为 $2$ 的细胞, $2$ 个长度为 $2$ 的细胞分为出 $2$ 个长度为 $1$ 的细胞, 这个过程一共有 $7$ 个细胞出现

提示

• $1\ \leq\ n \ \leq\ 10^{12}$