Problem A: 山楼粉堞隐悲笳

Problem A: 山楼粉堞隐悲笳

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 26  Solved: 14
[Submit][Status][Web Board]

Description

 叶穿云(字沈墙)楚地秀才,自幼精通算术。

李青琐(字达老)夔州名将,自幼习武。

 

李将军回乡省亲,在长安买特产带回家的时候不小心看错了价格,无奈只能尽量走水路,与一名叶姓书生同舟共济。

船至白帝城附近,两人听得城上面有胡笳声音传出,以为妙绝,登城拜访。

奏乐者乃一奇女子,她要来者回答出一个问题,否则无法一睹芳容。

女子为郎君准备了n份月饼,第i份的重量为i两。

在制作时候由于贪吃不慎吃去一份(不知道重量是多少了),现在只有n-1

女子将月饼都放在盒子里面,无法打开,而且放入的时候被不慎打乱了,

这是寄托着女子思念的月饼,她可以通过奏乐感应到月饼的灵性。

每次选取一个月饼奏乐,音符为i,可以知道对应的重量的二进制表示下面的第i位是不是0

“我们大唐怎么会知道二进制?”李将军问道。

“妾身认为,周易2.0是最好的逻辑系统。”

女子没有那么多时间,她只想知道,自己在最坏的情况下,至少需要吹奏多少次,才知道自己偷吃的月饼的份量(也可以理解为自己至少吹奏多少次保证能找出偷吃的月饼的份量)。

叶书生晃了晃脑袋,脱口而出答案,已经走了。

留下了李将军,

李将军自然是会算的,但是碍于情面,让你出马

你想被揍扁吗?不想,不想就给我算。

Input

输入仅一组数据

对于每一组数据,第一行输入一个整数N(2<=N<=1000000),代表有N份月饼。

Output

对于每一组数据输出一个数字,表示最少能找到偷吃月饼份量的次数。

Sample Input

5

Sample Output

7

HINT

[Submit][Status]