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

Условие

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

$G(0) = 0$

$G(n) = n - G(G(n - 1)),\,n \gt 0.$

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

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

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

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

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

Ограничения

$0 \le n \le 10^{5}$

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

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

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

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

$G(1)= 1 - G(G(1 - 1)) = 1 - G(G(0)) = 1 - G(0) = 1 - 0 = 1$.

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

1

1