Mỗi khi trời mưa, cánh đồng của Farmer John luôn bị ngập. Tuy nhiên, vì cánh đồng không hoàn toàn bằng phẳng nên nước dâng không đồng đều, để lại một số "hòn đảo" bị ngăn cách bởi những vùng nước rộng.

Cánh đồng của FJ được mô tả như một địa hình một chiều gồm \(N\) giá trị độ cao liên tiếp \(H(1) \ldots H(n)\) (\(1 \le N \le 100\,000\)). Giả sử địa hình được bao quanh bởi những hàng rào cao gần như vô hạn, hãy xét diễn biến khi có một trận mưa: những vùng thấp nhất bị nước phủ trước, tạo ra một số "hòn đảo" rời nhau; cuối cùng, tất cả chúng đều bị ngập khi mực nước tiếp tục dâng. Ngay khi mực nước bằng độ cao của một phần đất, phần đất đó được coi là đã ở dưới nước.

Hình trên minh họa một ví dụ: ở bên trái, lượng nước vừa vượt quá 1 đơn vị, để lại 4 hòn đảo (số lượng lớn nhất từng xuất hiện). Sau đó, khi tổng lượng nước đã dâng thêm là 7 đơn vị, ta có hình bên phải với chỉ hai hòn đảo còn nhô lên. Hãy tính số hòn đảo lớn nhất có thể xuất hiện tại cùng một thời điểm trong trận mưa, khi mực nước dâng cho đến lúc toàn bộ cánh đồng chìm dưới nước.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa độ cao \(H(i)\) (\(1 \le H(i) \le 1\,000\,000\,000\)).

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất cho biết số hòn đảo lớn nhất xuất hiện tại bất kỳ một thời điểm nào trong suốt trận mưa.

Ví dụ

8
3
5
2
3
1
4
2
3

4

Nguồn

USACO 2012 US Open, Bronze Division — Islands

Tác giả: Brian Dean, 2012.