8630번 - Ciąg 다국어

Jaś niedawno usłyszał w szkole o ciągach liczbowych. Bardzo mu się one spodobały i szybko zaczął tworzyć swoje własne, długie sekwencje liczb. Jego najnowszym wymysłem jest ciąg $a$ - niemalejąca sekwencja liczb naturalnych o następującej własności: dla każdej liczby naturalnej $k$ zawiera ona dokładnie $a_k$ wystąpień liczby $k$. (Zakładamy przy tym, że $0$ nie jest liczbą naturalną). Innymi słowy, dla każdego $k$ dokładnie $a_k$ spośród liczb $a_1, a_2, a_3, \dots$ jest równe $k$.

Pierwszych kilka wyrazów ciągu udało się Jasiowi wypisać, ale kartka i długopis okazały się niewystarczające, aby wygenerować jakiś dłuższy początkowy fragment ciągu. Pomóż Jasiowi uporać się z tym problemem.

Napisz program, który:

• wczyta ze standardowego wejścia liczbę naturalną $n$,
• wyznaczy $n$-ty wyraz ciągu $a$,
• wypisze wynik na standardowe wyjście.

Pierwszy i jedyny wiersz wejścia zawiera jedną liczbę naturalną $n$ ($1 ≤ n ≤ 10^{18}$) - numer szukanego wyrazu ciągu.

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę naturalną $a_n$.

$a_5 = 3$ oznacza, że w ciągu $a$ liczba $5$ występuje dokładnie $3$ razy; dokładniej, $a_9 = a_{10} = a_{11} = 5$.