Giải bài trực tuyến

Cho dãy số nguyên dương a₁, a₂, ..., a_n.

Dãy số: a_i, a_i+1, ..., a_j thỏa mãn a_i ≤ a_i+1 ≤ ... ≤ a_j. Với 1 ≤ i ≤ j ≤ n được gọi là dãy con không giảm của dãy số đã cho và khi đó số j-i+1 được gọi là độ dài của dãy con này.

Yêu cầu: Trong số các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy số {u_k} xác định bởi u₁ = 1, u_{k = uk-1} + k (k ≥ 2), hãy tìm dãy con có độ dài lớn nhất.

Input

Dòng đầu tiên chứa một số nguyên dương n (n ≤ 10⁴).

Dòng thứ i trong n dòng tiếp theo chứa một số nguyên dương a_i (a_i ≤ 10⁸) là số hạng thứ i của dãy số đã cho, i = 1, 2, ..., n.

Output

Gồm 1 dòng duy nhất ghi số nguyên d là độ dài của dãy con không giảm tìm được (quy ước rằng nếu không có dãy con nào thỏa mãn điều kiện đặt ra thì d = 0).

Example

Input:
8
2
2007
6
6
15
16
3
21
Output:
3