hof

Să considerăm secvenţa $\{ a_n \}$ unde:

• $a_1 = 1$;
• secvenţa este crescătoare, adică. $a_k > a_{k-1}$ pentru orice $k > 1$;
• diferenţele de ordin $I$ sunt crescătoare, adică $a_k – a_{k-1} > a_{k-1} – a_{k-2}$ pentru orice $i > 2$;
• Termenii din secvenţă şi diferenţele de ordin $I$ acoperă în mod unic mulţimea numerelor naturale nenule (adică orice număr natural nenul apare fie în secvenţa $\{ a_n \}$, fie în secvenţa diferenţelor de ordin $I$ dar nu în amândouă secvenţele).

Astfel $a = \{ 1, 3, 7, 12, 18, 26, 35, 45, ... \}$, iar diferenţele de ordin $I$ sunt $\{ 2, 4, 5, 6, 8, 9, 10, ... \}$. Aceste două secvenţe sunt disjuncte şi acoperă mulţimea numerelor naturale nenule.

Cerinţă

Dat $n$ număr natural, să se determine $a_n$.

Date de intrare

Fişierul de intrare hof.in conţine o singură linie pe care se află numărul natural $n$.

Date de ieşire

Fişierul de ieşire hof.out conţine o singură linie pe care se află numărul natural $a_n$, reprezentând al $n$-lea termen din secvenţa Hofstadter.

Restricții și precizări

• $1 \leq n \leq 1 \ 000 \ 000$;

Exemplu

hof.in

5

hof.out

18