P8676 [Lanqiao Cup 2018 National A] Self-Describing Sequence

Xiaoming is studying a sequence called the Golomb self-describing sequence, denoted as $G(n)$. This sequence has two interesting properties: 1. For any positive integer $n$, $n$ appears in the whole sequence exactly $G(n)$ times. 2. This sequence is non-decreasing. The following are the first few terms of $G(n)$: $n$|1|2|3|4|5|6|7|8|9|10|11|12|13 -|-|-|-|-|-|-|-|-|-|-|-|-|- $G(n)$|1|2|2|3|3|4|4|4|5|5|5|6|6 Given an integer $n$, can you help Xiaoming compute the value of $G(n)$?

An integer $n$.

Output one integer, which is the answer.

For $30\%$ of the testdata, $1 \le n \le 10^6$. For $70\%$ of the testdata, $1 \le n \le 10^9$. For $100\%$ of the testdata, $1 \le n \le 2\times 10^{15}$. Time limit: 1 second, 256 MB. Lanqiao Cup 2018, the 9th National Finals. Translated by ChatGPT 5