Задача E. Golomb sequence ≡

Условие

Последовательностью Голомба называется последовательность неубывающих натуральных чисел a_n такая, что значение a_n равно количеству повторений числа n в этой последовательности, при этом a₁ = 1, a₂ = 2 и a_n выбирается как минимально возможное число, удовлетворяющее свойству последовательности и a_n ⩾ a_n − 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, …

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

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

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

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

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

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

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

Ограничения

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

• 10 тестов, 1 балл за тест, 1 ⩽ n ⩽ 50
• 10 тестов, 1 балл за тест, 51 ⩽ n ⩽ 999
• 5 тестов, 4 балла за тест, 1000 ⩽ n ⩽ 10⁶

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

10

5

50

13