Задача M. Mountain ≡

Условие

Гора представлена двоичной кучей на n вершинах. Также есть число k, которое равно сумме расстояний между всеми парами вершин. Зная k, найдите n.

Двоичной кучей в данной задаче называется неориентированное двоичное дерево, для которого выполнены следующие условия:

• Каждая вершина имеет не более трех соседей
• Глубина всех листьев (расстояние до корня) различается не более чем на 1 слой.
• Последний слой заполняется слева направо без «дырок».

К примеру, двоичная куча на 4 вершинах:

Формат входных данных

Единственная строка входных данных содержит натуральное число k.

Формат выходных данных

Выведите n.

Ограничения

0 ≤ k ≤ 10¹⁸

Пояснение к примеру

Расстояние между 1-ой и 2-ой вершиной равно 1. Расстояние между 1-ой и 3-ой вершиной равно 1. Расстояние между 1-ой и 4-ой вершиной равно 2. Расстояние между 2-ой и 3-ой вершиной равно 2. Расстояние между 2-ой и 4-ой вершиной равно 1. Расстояние между 3-ой и 4-ой вершиной равно 3. Сумма всех расстояний равна 1 + 1 + 2 + 2 + 1 + 3 = 10.

Примеры тестов

10

4