Sequência de Hofstadter-Conway

A sequência recursiva de Hofstadter-Conway é definida pela relação de recorrência $$a(n) = a(a(n-1)) + a(n - a(n-1)),$$ com $a(1) = a(2) = 1$. Os primeiros valores da sequência são 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, ….

Conway demonstrou, em 1988, que $\lim_{n\to\infty} a(n)/n = 1/2$ e ofereceu um prêmio de 10 mil dólares para o primeiro que determinasse um valor de $n$ para o qual $\vert a(i)/i - 1/2\vert \leq 1/20$, para $i > n$. O prêmio foi conquistado por Mallows, após Conway ter ajustado o prêmio intencionado para mil dólares. O valor de $n$ era igual a 1489.

Dado o valor de $n$, determine o $n$-ésimo termo da sequência recursiva de Hofstadter-Conway.

Entrada

A entrada consiste em uma única linha, contendo o valor de $n$ ($1\leq n\leq 2\times 10^5$).

Saída

Imprima, em uma linha, o valor de $a(n)$.

Exemplo de entrada 1

3

Exemplo de saída 1

2

Exemplo de entrada 2

5

Exemplo de saída 2

3

Exemplo de entrada 3

20

Exemplo de saída 3

12

Exemplo de entrada 4

50

Exemplo de saída 4

29