Mô tả bài toán

Quần đảo Nhật Bản là một quần đảo hẹp và dài. Quần đảo Nhật Bản được chia thành $N$ khu vực bởi các đường ranh giới song song. Các khu vực được đánh số lần lượt từ $1$ đến $N$ tính từ một đầu. Độ cao của khu vực $i$ ($1 \le i \le N$) là $A_i$.

Quần đảo Nhật Bản được bao quanh bởi biển, và mực nước biển là không đổi bất kể vị trí. Một khu vực có độ cao lớn hơn hẳn mực nước biển được gọi là đất liền.

Một phần đất liền liên tiếp được gọi là một hòn đảo. Chính xác hơn thì như sau: Với hai số nguyên $l$, $r$ ($1 \le l \le r \le N$), phần của quần đảo Nhật Bản gồm khu vực $l$, khu vực $l+1$, $\dots$, khu vực $r$ được gọi là vùng $[l, r]$. Một vùng $[l, r]$ thỏa mãn các điều kiện sau đây được gọi là một hòn đảo:

• Khu vực $l$, khu vực $l+1$, $\dots$, khu vực $r$ đều là đất liền.
• Nếu $l > 1$ thì khu vực $l-1$ không phải là đất liền.
• Nếu $r < N$ thì khu vực $r+1$ không phải là đất liền.

Do mực nước biển dâng cao, quần đảo Nhật Bản đang chìm dần từng chút một. Mực nước biển hiện tại là $0$, nhưng theo thời gian nó sẽ dâng lên từ từ, và cuối cùng toàn bộ Nhật Bản sẽ biến thành biển.

JOI nhận thấy rằng khi mực nước biển dâng lên, số lượng hòn đảo của Nhật Bản sẽ tăng giảm. Hãy tìm giá trị lớn nhất của số lượng hòn đảo trong khoảng thời gian từ hiện tại cho đến khi Nhật Bản không còn đất liền nữa (tính cả thời điểm hiện tại).

Ràng buộc

• $1 \le N \le 100000 (= 10^5)$
• $0 \le A_i \le 1000000000 (= 10^9)$ ($1 \le i \le N$)

Dữ liệu vào và Kết quả

Dữ liệu vào
Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:
$N$
$A_1$ $A_2$ $\dots$ $A_N$

Kết quả
In ra trên $1$ dòng giá trị lớn nhất của số lượng hòn đảo trong khoảng thời gian từ hiện tại cho đến khi Nhật Bản không còn đất liền nữa (tính cả hiện tại).

Subtask

1. ($7$ điểm) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$ điểm) $N \le 2000$
3. ($85$ điểm) Không có ràng buộc bổ sung.

Ví dụ

Đầu vào mẫu 1

6
0 1 2 1 3 2

Đầu ra mẫu 1

2

• Khi mực nước biển từ $0$ đến dưới $1$, các khu vực $2, 3, 4, 5, 6$ là đất liền. Vì vùng $[2, 6]$ là hòn đảo duy nhất nên số lượng đảo là $1$.
• Khi mực nước biển từ $1$ đến dưới $2$, các khu vực $3, 5, 6$ là đất liền. Vì vùng $[3, 3]$ và vùng $[5, 6]$ là các hòn đảo nên số lượng đảo là $2$.
• Khi mực nước biển từ $2$ đến dưới $3$, chỉ có khu vực $5$ là đất liền. Vì vùng $[5, 5]$ là hòn đảo duy nhất nên số lượng đảo là $1$.
• Khi mực nước biển đạt tới $3$, không còn đất liền nào nữa và số lượng đảo trở thành $0$.

Do đó giá trị lớn nhất của số lượng đảo là $2$, nên in ra $2$.

Đầu vào mẫu 2

6
3 2 3 0 2 0

Đầu ra mẫu 2

2

• Khi mực nước biển từ $0$ đến dưới $2$, các khu vực $1, 2, 3, 5$ là đất liền. Vì vùng $[1, 3]$ và vùng $[5, 5]$ là các hòn đảo nên số lượng đảo là $2$.
• Khi mực nước biển từ $2$ đến dưới $3$, các khu vực $1, 3$ là đất liền. Vì vùng $[1, 1]$ và vùng $[3, 3]$ là các hòn đảo nên số lượng đảo là $2$.
• Khi mực nước biển đạt tới $3$, không còn đất liền nào nữa và số lượng đảo trở thành $0$.

Do đó giá trị lớn nhất của số lượng đảo là $2$, nên in ra $2$.

Đầu vào mẫu 3

10
4 1 2 1 2 3 5 4 3 2

Đầu ra mẫu 3

3