Problem Description

Xiaoming is playing a small jumping-stones game with his friends. There are $n$ stones in a row, numbered from $1$ to $n$. The $i$-th stone has a positive integer weight value $c_i$ written on it.

If at some moment Xiaoming is on stone $j$, then he may choose to jump to stone $j + c_j$ (provided that $j + c_j \le n$), or jump to stone $2j$ (provided that $2j \le n$). If there is no stone he can jump to, the game ends.

Suppose Xiaoming chooses to start jumping from stone $x$. If a stone may be visited by Xiaoming (where “visited” means that there exists some moment when Xiaoming is on this stone), then the weight value of this stone is included in the score set $S_x$. Then Xiaoming’s score when starting from stone $x$ is $|S_x|$.

For example, if Xiaoming starts from stone $x$ and the weight values on all stones that may be visited are $5, 3, 5, 2, 3$, then $S_x = \{5, 3, 2\}$ and the score is $|S_x| = 3$. Xiaoming may choose any stone to start from. Please compute the maximum score Xiaoming can obtain.

Input Format

The input has $2$ lines.

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $c_1, c_2, \cdots, c_n$, separated by spaces.

Output Format

The output has $1$ line, containing one integer, which is the answer.

5
4 3 5 2 1

4

Hint

Sample Explanation

Starting from the first stone gives the maximum score. The possible paths are as follows:

1. Stone $1$ $\to$ stone $5$: choose to jump from stone $1$ to stone $1 + c_1 = 5$.
2. Stone $1$ $\to$ stone $2$ $\to$ stone $5$: first choose to jump from stone $1$ to stone $2 \times 1 = 2$, then choose to jump from stone $2$ to stone $2 + c_2 = 5$.
3. Stone $1$ $\to$ stone $2$ $\to$ stone $4$: first choose to jump from stone $1$ to stone $2 \times 1 = 2$, then choose to jump from stone $2$ to stone $2 \times 2 = 4$.

Therefore, the set of weight values of all stones that may be visited is $S_1 = \{c_1, c_2, c_4, c_5\} = \{4, 3, 2, 1\}$, and the score is $|S_1| = 4$.

Constraints

For $20\%$ of the testdata, it is guaranteed that $n \le 20$.
For $100\%$ of the testdata, it is guaranteed that $n \le 40000$ and $c_i \le n$.

Translated by ChatGPT 5