В фантастическом лесу живут различные существа, каждое из которых имеет свой уникальный номер, начинающийся с 1. Также у каждого существа есть свой уровень энергии, представленный целым числом. У первого существа уровень энергии равен 1. Каждое последующее существо имеет уровень энергии, который зависит от уникального номера существа. В общем виде уровень энергии существа можно выразиить следующим образом:
creature[1] = 1creature[2 * i] = creature[i], если 2 <= 2 * i <= ncreature[2 * i + 1] = creature[i] + creature[i + 1], при 2 <= 2 * i + 1 <= n
Чтобы понять, насколько могущественны существа в лесу, необходимо найти существо с максимальным уровенем энергии.
Входные данные
Программа получает на вход натуральное число n (
1 <= n <= 100) - количество существ в фантастическом лесу.
Выходные данные
Выведите максимальный уровень энергии среди всех существ в данном фантастическом лесу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 |
1 |
| 2 |
7 |
3 |
| 3 |
3 |
2 |