#2034. 新约瑟夫游戏

新约瑟夫游戏

Description

你一定听说过经典的“约瑟夫”问题吧?现在来组织一个皆大欢喜的新游戏(图9.4-5):

image

假设n个人站成一圈,从第1人开始交替的去掉游戏者,但只是暂时去掉(例如,首先去掉2),直到最后剩下唯一的幸存者为止。幸存者选出后,所有比幸存者号码高的人每人将得到1块钱,并且永久性地离开,其余剩下的人将重复以上过程,比幸存者号码高的人每人将得到1块钱后离开。一旦经过这样的过程后,人数不再减少,最后剩下的那些人将得到2块钱。请计算一下组织者一共要付出多少钱?

如图9.4-5所示,第一轮有5人,幸存者是3,所以4、5得到1块钱后离开,下一轮幸存者仍然是3,因此没有人离开,所以每人得到2块钱,总共要付出2+2*3=8块钱。

Format

Input

一行一个整数n,不超过32767。

Output

一行一个整数,不超过65535,表示总共要付出多少钱。

Samples

10
13

Limitation

1s, 64MB for each test case.

Statistics

Related

In following homework:

1124作业