Задача №1815. Гребешок Бабы-Яги
Сослужив службу морскому царю, Иван-царевич пошёл на прогулку. Шёл он, шёл по дороге, приметил впереди дерево. И вдруг, откуда ни возьмись, возле дерева появилась страшная Баба-Яга! Достала из лохмотьев гребешок, помахала им — и вместо одного дерева стал поперёк дороги дремучий лес. Так Баба-Яга решила заманить Ивана-царевича в своё логово, чтобы там зажарить и съесть его.
Но и тут не забыла про Ивана-царевича Василиса Премудрая. Послала птичку, чтобы та посмотрела, далеко ли простирается дремучий лес, можно ли сквозь него пройти. Вернулась птичка к Ивану-царевичу и говорит человеческим голосом:
— Не ходи в этот лес, Иван-царевич, погубит тебя Баба-Яга! В лесу этом n деревьев, кроны тёмные, стволы толстые — заблудишься и сгинешь!
Иван-царевич уже встречался с Бабой-Ягой и знает, что гребешок у неё волшебный: каждый раз, когда Баба-Яга махнёт своим гребешком, каждое дерево в лесу становится столькими деревьями, сколько зубьев в этом гребешке. К примеру, если зубьев всего два, то махнёт Баба-Яга гребешком, и из одного дерева станет два; ещё махнёт, и будет четыре дерева; ещё махнёт, и будет восемь. Заколдованность леса такова, сколько раз Баба-Яга махнула своим гребешком. Чем больше заколдованность леса, тем темнее кроны деревьев, толще стволы, тем труднее сквозь него пройти и не заблудиться.
Крепко задумался Иван-царевич: идти ли ему сквозь дремучий лес. Попробуйте его ободрить, вычислив, какова максимальная заколдованность этого леса. Имейте в виду, что в гребешке Бабы-Яги может быть очень много зубьев!
В первой строке входного файла задано одно целое число n — количество деревьев в заколдованном лесу (2 \(\le\) \(n\) \(\le\) \(10^9\)).
В первой строке выходного файла выведите одно число — максимальную заколдованность этого леса.
12
1
4
2