Задача 69. Единица! Кому она нужна?! ≡

Условие

...

Единица — вздор, единица — ноль

...

Владимир Маяковский, поэма "Владимир Ильич Ленин", 1924 г.

Недавно на уроке информатики Тимофей узнал про двоичную систему счисления. Больше всего ему понравились двоичные числа, имеющие следующее представление: сначала идет группа единиц, потом группа нулей, потом снова группа единиц (под группой будем понимать любое натуральное количество элементов). Такие числа Тимофей называет 101-образными и старательно выписывает их в столбик в порядке возрастания.

Какое десятичное число, запись которого в двоичной системе счисления 101-образна, будет располагаться на n-ом месте в списке?

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

В единственной строке записано одно натуральное число n — порядковый номер 101-образного числа.

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

Выведете одно натуральное число — соответствующее десятичное число.

Ограничения

1 ≤ n ≤ 20000

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: 0 ≤ n ≤ 500, баллы: 30. Гарантируется, что ответ не превысит 10⁵.

Подзадача 2: нет дополнительных ограничений, баллы: 70. Гарантируется, что ответ не превысит 10¹⁸.

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

Комментарий к первому примеру: приведем ряд из десяти первых чисел, представление которых в двоичной системе счисления 101-образно:

5₁₀ = 101₂;

9₁₀ = 1001₂;

11₁₀ = 1011₂;

13₁₀ = 1101₂;

17₁₀ = 10001₂;

19₁₀ = 10011₂;

23₁₀ = 10111₂;

25₁₀ = 11001₂;

27₁₀ = 11011₂;

29₁₀ = 11101₂.

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

10

29