일본 침몰 (Japan Sinks)

일본 열도는 길쭉한 열도이다. 일본 열도는 평행한 경계선에 의해 N개의 구역으로 나뉘어 있다. 구역에는 끝에서부터 순서대로 1부터 N까지의 번호가 붙어 있다. 구역 i (1 ≤ i ≤ N)의 높이는 A_i이다.

일본 열도는 바다에 둘러싸여 있고, 해수면의 높이는 장소에 관계없이 일정하다. 높이가 해수면의 높이보다 높은 구역을 육지라고 한다.

육지가 연속되어 있는 부분을 섬이라고 한다. 더 정확히 쓰면 다음과 같다. 정수 l, r (1 ≤ l ≤ r ≤ N)에 대해, 일본 열도 중 구역 l, 구역 l+1, ..., 구역 r로 이루어진 부분을 영역 [l, r]이라고 한다. 다음 조건을 만족하는 영역 [l, r]을 섬이라고 한다:

• 구역 l, 구역 l+1, ..., 구역 r은 모두 육지이다.
• l>1이면 구역 l-1은 육지가 아니다.
• r<N이면 구역 r+1은 육지가 아니다.

해수면 상승으로 일본 열도는 조금씩 침몰하고 있다. 현재 해수면의 높이는 0이지만, 이는 시간이 지날수록 점차 올라가고, 마침내 일본 전체가 바다가 된다.

JOI 군은 해수면의 높이가 상승하면 일본의 섬의 수가 늘었다 줄었다 한다는 것을 깨달았다. 현재부터 일본에 육지가 없어질 때까지의 기간(현재 포함)에서 섬의 수의 최댓값을 구하고 싶다.

입력은 다음 형식으로 표준 입력에서 주어진다.

N
A_1 A_2 ... A_N

현재부터 일본에 육지가 없어질 때까지의 기간(현재 포함)에서 섬의 수의 최댓값을 1행으로 출력하라.

• 1 ≤ N ≤ 100000 (= 10^5)
• 0 ≤ A_i ≤ 1000000000 (= 10^9) (1 ≤ i ≤ N)