无尽大军
题号：NC54604
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

恭喜你，勇士。如果你过关斩将来到了这一题面前，那么说明你具有非凡的才华。现在你将面临最终的考验，为了对抗最后也是最强大的敌人，你需要组建一支属于你自己的军队。
你将组建一支魔法军队。一开始只有一名士兵，但是每次你可以使用两种法术来扩大你的军队的规模。
  • A: 消耗2点法力值将你的军队规模翻倍，这意味着你的军队规模将会从k扩大至2k——增加了k名士兵。
  • B: 如果你之前使用过法术，那么你可以消耗1点法力值重现你上一次法术的效果。这意味着如果上一次使用法术时你的军队规模增加了k，那么你的军队会再增加k名士兵。
虽然你现在拥有无比强大的法力，但这并不意味着可以随便浪费——毕竟你不知道你最后的敌人究竟有多么强大。事实上你希望消耗最少的法力值就能让你的军队的规模达到。

输入描述:

输入一个整数。

输出描述:

输出一个整数，表示你的军队规模达到n所需要消耗的最少法力值。
示例1

输入

复制 
1

输出

复制 
0
示例2

输入

复制 
6

输出

复制 
5

说明

一开始你的军队只有一名士兵，消耗2点法力值使你的军队规模翻倍。于是现在你有了两名士兵，再消耗1点法力值使军队达到3人。此时再消耗2点法力值就能达到6人。一共消耗5点法力值。