Description

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)$:

Given an integer $n$, can you help Xiaoming compute the value of $G(n)$?

Input Format

An integer $n$.

Output Format

Output one integer, which is the answer.

13

6

Hint

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