Задача E. Golomb sequence

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:40  

Условие

Последовательностью Голомба называется последовательность неубывающих натуральных чисел an такая, что значение an равно количеству повторений числа n в этой последовательности, при этом a1 = 1, a2 = 2 и an выбирается как минимально возможное число, удовлетворяющее свойству последовательности и an⩾ an − 1. Таким образом, первыми элементами последовательности являются

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, …

Общий член последовательности при этом может быть вычислен как

an = a(n) = 1 + a(n − a(a(n − 1))),  n > 1 .

Требуется для заданного числа nN вычислить элемент последовательности an.

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

Первая строка входного файла содержит единственное натуральное число n.

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

Выходной файл должен содержать единственное натуральное число an.

Ограничения

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

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

Стандартный вход Стандартный выход
1
10
5
2
50
13

0.083s 0.015s 13