#551. 新的黑板游戏

新的黑板游戏

题目描述

之前有一个黑板游戏的题目,那今天继续玩黑板游戏。这次的黑板游戏跟上次的不一样咯。

这次还是在黑板写一下一个正数nn,然后呢给你留了一个作业,你可以给陈老师xx元然后你可以把一个数字xx擦去,但是如果你擦掉了一个xx,那么你需要再在黑板上写一个x/2x / 2下取整和x/2x / 2上取整。那么这样你肯定会觉得陈老师太欺负人啦,那么如果你可以使得黑板上没有大于等于22的数字就算你完成作业咯。不过你的零花钱是有限的,所以你要想一个办法需要给陈老师最少的钱去完成这个作业。

样例输入

第一行一个整数nn

样例输出

输出一个整数作为答案。

样例

样例一

3
5

样例解释:

  1. 擦去33写上1122花费33
  2. 擦去22写上1111花费22

数据范围

2n10172 \le n \le 10^{17}