慈善的约瑟夫

题目描述

你一定听说过约瑟夫问题吧?即从N个人中找出唯一的幸存者。现在老约瑟夫将组织一个皆大欢喜的新游戏,假设N个人站成一圈,从第1人开始交替的去掉游戏者,但只是暂时去掉,直到最后剩下唯一的幸存者为止。幸存者选出后,所有比幸存者号码高的人每人得到1个金币,永久性离开。其余剩下的将重复以上的游戏过程,比幸存者号码主的人每人得到1个金币后离开。经过这们的过程后,一旦人数不再减少,则最后剩下的那些人将得到2个金币。请你计算一下老约瑟夫一共要付出多少钱?

输入输出格式

输入格式


一行一个正整数N表示人数。

输出格式


一行一个正整数表示共需支付的钱数。

输入输出样例

输入样例 #1

10

输出样例 #1

13

说明

1<=N<=100000