Minh đang chơi trò nhảy đá cùng các bạn, có tổng cộng $n$ hòn đá xếp thành một hàng theo thứ tự từ $1$ đến $n$, hòn đá thứ $i$ có ghi trọng số nguyên dương $c_i$.

Nếu tại một thời điểm nào đó Minh đang ở hòn đá thứ $j$, thì cậu có thể chọn nhảy đến hòn đá thứ $j + c_j$ (với điều kiện $j + c_j \le n$) hoặc nhảy đến hòn đá thứ $2j$ (với điều kiện $2j \le n$), khi không còn mục tiêu nào để nhảy thì trò chơi kết thúc.

Giả sử Minh chọn bắt đầu nhảy từ hòn đá thứ $x$, nếu một hòn đá nào đó có khả năng được Minh đi qua (“đi qua” nghĩa là tồn tại một thời điểm Minh đứng ở hòn đá đó), thì trọng số của hòn đá này được đưa vào tập điểm $S_x$, khi đó điểm số của Minh khi bắt đầu nhảy từ hòn đá thứ $x$ là $|S_x|$.

Ví dụ nếu Minh xuất phát từ hòn đá thứ $x$, trọng số trên tất cả các hòn đá có thể đi qua lần lượt là $5,3,5,2, 3$, thì $S_x = {5, 3, 2}$ và điểm số là $|S_x| = 3$. Minh có thể tùy ý chọn một hòn đá để bắt đầu nhảy, hãy tìm số điểm lớn nhất mà Minh có thể đạt được.

Dữ liệu vào

Đầu vào gồm $2$ dòng.

Dòng đầu tiên là một số nguyên dương $n$.

Dòng thứ hai là $n$ số nguyên dương $c_1, c_2,\cdots, c_n$ cách nhau bởi dấu cách.

Dữ liệu ra

Đầu ra gồm $1$ dòng, một số nguyên biểu thị đáp án.

Ví dụ

Input

5
4 3 5 2 1

Output

4

Ghi chú

Giải thích ví dụ

Xuất phát từ hòn đá thứ nhất được nhiều điểm nhất, có các đường đi sau:

1. Hòn $1$ $\to$ hòn $5$: chọn nhảy từ hòn $1$ đến hòn $1 + c_1=5$.
2. Hòn $1$ $\to$ hòn $2$ $\to$ hòn $5$: lần thứ nhất chọn nhảy từ hòn $1$ đến hòn $2 \times 1=2$, lần thứ hai chọn nhảy từ hòn $2$ đến hòn $2 + c_2 = 5$.
3. Hòn $1$ $\to$ hòn $2$ $\to$ hòn $4$: lần thứ nhất chọn nhảy từ hòn $1$ đến hòn $2 \times 1=2$, lần thứ hai chọn nhảy từ hòn $2$ đến hòn $2 \times 2 = 4$.

Vì vậy tập trọng số của tất cả các hòn đá có thể đi qua là $S_1 = {c_1, c_2, c_4, c_5} = {4, 3, 2, 1}$, điểm số là $|S_1| = 4$.

Phạm vi dữ liệu

Với $20\%$ số test, đảm bảo $n \le 20$.
Với $100\%$ số test, đảm bảo $n \le 40000$, $c_i \le n$.

Nguồn: Lanqiao Cup 2024, vòng chung kết quốc gia bảng B