Xâu chuỗi vỏ ốc

Sắn dạo dọc bờ biển và lần lượt nhìn thấy \(n\) chiếc vỏ ốc, chiếc thứ \(i\) có kích thước \(a_i\). Bạn ấy muốn xâu một số vỏ ốc thành một chuỗi theo cách sau:

• Ban đầu chuỗi rỗng.
• Với mỗi vỏ ốc gặp theo thứ tự, Sắn có thể bỏ qua, hoặc xâu vào đầu trái của chuỗi, hoặc xâu vào đầu phải của chuỗi (chiếc đầu tiên được lấy thì chuỗi chỉ có một vỏ).
• Khi kết thúc, đọc chuỗi từ trái sang phải thì kích thước các vỏ ốc phải tăng ngặt (\(a\) bên trái nhỏ hơn hẳn \(a\) bên phải liền kề).

Hãy tìm số vỏ ốc lớn nhất có thể có trong chuỗi.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\).

Output

In ra một số nguyên là số vỏ ốc lớn nhất của chuỗi.

Constraints

• \(1 \le n \le 5000\)
• \(0 \le a_i \le 10^9\)

Sample Input 1

6
3 5 3 2 6 1

Sample Output 1

5

Sample Input 2

8
6 2 9 4 4 5 8 1

Sample Output 2

5

Explanation

Ví dụ 1: lấy \(3\); lấy \(5\) xâu bên phải (chuỗi \(3, 5\)); bỏ qua \(3\); lấy \(2\) xâu bên trái (\(2, 3, 5\)); lấy \(6\) xâu bên phải (\(2, 3, 5, 6\)); lấy \(1\) xâu bên trái (\(1, 2, 3, 5, 6\)).

Ví dụ 2: bỏ \(6\), lấy \(2\); lấy \(4\) xâu bên phải, bỏ chiếc \(4\) thứ hai, lấy \(5\), rồi \(8\) xâu bên phải (\(2, 4, 5, 8\)); cuối cùng lấy \(1\) xâu bên trái (\(1, 2, 4, 5, 8\)).