Cho một dãy số \(A\) gồm \(n\) số nguyên dương \(a_1, a_2, a_3...a_n\) mỗi số có giá trị không quá \(10^9\). Một dãy con từ \(l\) đến \(r (l \le r)\) được gọi là một dãy cân bằng nếu \(a_1 \ge 1, a_{i+1} \ge 2, ... a_r \ge (r-l+1)\). Hãy xác định độ dài dãy con cân bằng dài nhất của dãy số đã cho.

Dữ liệu vào:

• Dòng đầu tiên gồm duy nhất một số nguyên dương \(n (1 \le n \le 10^5)\);
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2... a_n\) được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra: một số duy nhất là độ dài dãy con tìm được.

Ràng buộc:

• 35% số test ứng với 35% số điểm có \(n \le 200 \)
• 15% số test ứng với 15% số điểm có \(n \le 5 \times 10^3 \)
• 50% số test ứng với 50% số điểm còn lại và không có ràng buộc gì thêm.

Input

6
2 1 1 4 3 6

Output

4

Giải thích

Dãy con cân bằng dài nhất là 1, 4, 3, 6 (l=3, r=6 và độ dài bằng 4)