Задача E. Последовательность G Хофштадтера ≡

Условие

Последовательность G Хофштадтера определяется следующим образом:

G(0) = 0

G(n) = n − G(G(n − 1)), n > 0.

По данному n определите G(n).

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

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

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

0 ≤ n ≤ 10⁵

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

Баллы за каждый тест начисляются независимо.

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

В примере дано n = 1.

G(1) = 1 − G(G(1 − 1)) = 1 − G(G(0)) = 1 − G(0) = 1 − 0 = 1.

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

1

1