Nhặt ốc ven biển

Trên bãi biển, Sắn đi thẳng một đường và gặp lần lượt \(n\) chiếc vỏ ốc với kích thước \(a_1, a_2, \dots, a_n\). Bạn ấy muốn nối một số chiếc lại thành một chuỗi theo luật 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 10^5\)
• \(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\)).