0376. Последовательность доктора Монта

\epigraph{Михаил Афанасьевич Монт – ведущий специалист в области комбинаторных последовательностей, доктор физико-математических наук}

Доктор Монт совершил научный прорыв в области комбинаторных последовательностей! Открытая им последовательность поможет приблизиться к решению задачи об оптимальной нумерации произвольных объектов, более известной как задача <<О n слонах>>. Благодаря этому открытию Михаил Афанасьевич, возможно, получит Елефантовскую премию – самую престижную премию в области комбинаторных последовательностей.
Однако, М. А. Монту нужна ваша помощь – для более детального изучения последовательности ему нужно получить n--ый элемент этой последовательности, при этом n может быть очень велико!
Как? Вы не знаете формулу этой последовательности? Вы что, с Земли упали? Ладно, уговорили, мы напомним вам её определение.
Последовательность a называется последовательностью М. А. Монта, если выполняется следующее:

1. a₁ = 1;
2. Последовательность a – строго возрастающая, то есть для любого n > 1 выполняется a_n > a_{n - 1};
3. Для любого n > 1, a_n – наименьшее положительное число такое, что a_an = n.

Спешите! У вас есть всего несколько часов для того, чтобы помочь доктору Монту!

Формат входного файла

В единственной строке входного файла задано натуральное число n (1 ≤ n ≤ 10⁹) – порядковый номер элемента в последовательности, который требуется Михаилу Афанасьевичу Монту.

Формат выходного файла

В единственной строке выходного файла выведите a_n.

Пример:

Источник: Открытый весенний чемпионат ПетрГУ по программированию, 20 апреля 2014

Обсудить       Отправить решение



Версия для печати