Quần đảo Nhật Bản có hình dạng dài và hẹp. Các đường ranh giới song song chia quần đảo thành \(N\) vùng, được đánh số từ \(1\) đến \(N\) theo thứ tự từ một đầu đến đầu còn lại. Vùng \(i\) có độ cao \(A_i\), với \(1 \le i \le N\).

Quần đảo được biển bao quanh, và mực nước biển tại mọi nơi đều bằng nhau. Một vùng được gọi là đất liền nếu độ cao của nó lớn hơn mực nước biển.

Một phần đất liền liên tiếp được gọi là một đảo. Chính xác hơn, với các số nguyên \(l,r\) thỏa mãn \(1 \le l \le r \le N\), gọi phần gồm các vùng \(l,l+1,\ldots,r\) là đoạn \([l,r]\). Đoạn này là một đảo nếu thỏa mãn tất cả các điều kiện sau:

• Các vùng \(l,l+1,\ldots,r\) đều là đất liền.
• Nếu \(l>1\), vùng \(l-1\) không phải là đất liền.
• Nếu \(r<N\), vùng \(r+1\) không phải là đất liền.

Do mực nước biển dâng lên, Nhật Bản đang dần chìm xuống. Mực nước biển hiện tại bằng \(0\); theo thời gian, nó tăng dần cho đến khi toàn bộ Nhật Bản bị ngập.

JOI nhận thấy số đảo có thể tăng hoặc giảm khi mực nước biển dâng. Hãy tìm số đảo lớn nhất trong khoảng thời gian từ hiện tại cho đến khi không còn đất liền, tính cả thời điểm hiện tại.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

N
A_1 A_2 ... A_N

Dữ liệu ra

In ra một dòng chứa số đảo lớn nhất trong khoảng thời gian đã nêu.

Ràng buộc

• Các giá trị đầu vào đều là số nguyên.
• \(1 \le N \le 10^5\).
• \(0 \le A_i \le 10^9\) với \(1 \le i \le N\).

Phân nhóm

1. Nhóm 1 (7 điểm): \(1 \le N \le 2000\) và \(0 \le A_i \le 2000\) với mọi \(1 \le i \le N\).
2. Nhóm 2 (8 điểm): \(1 \le N \le 2000\) và \(0 \le A_i \le 10^9\) với mọi \(1 \le i \le N\).
3. Nhóm 3 (85 điểm): \(1 \le N \le 10^5\) và \(0 \le A_i \le 10^9\) với mọi \(1 \le i \le N\).

Ví dụ

6
0 1 2 1 3 2

2

6
3 2 3 0 2 0

2

10
4 1 2 1 2 3 5 4 3 2

3

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật, đối chiếu với bản trên AtCoder, của Ủy ban Olympic Tin học Nhật Bản, vòng loại JOI 2018/2019. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.