문제 설명

일본 열도는 가늘고 긴 열도이다. 일본 열도는 평행한 경계선에 의해 $N$개의 구획으로 나뉘어 있다. 구획에는 한쪽 끝에서부터 순서대로 $1$부터 $N$까지의 번호가 붙어 있다. 구획 $i$ ($1 \le i \le N$)의 높이는 $A_i$이다.

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

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

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

해수면 상승으로 인해 일본 열도는 조금씩 침몰하고 있다. 현재 해수면의 높이는 $0$이지만, 이는 시간이 지남에 따라 서서히 올라가 마침내 일본 전체가 바다가 되어 버린다.

JOI 군은 해수면의 높이가 상승함에 따라 일본의 섬의 개수가 증감한다는 것을 깨달았다. 현재부터 일본에 육지가 없어질 때까지의 기간(현재 포함) 동안 섬의 개수의 최댓값을 구하고자 한다.

제약 조건

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

입출력

입력
입력은 다음 형식으로 표준 입력에서 주어진다.
$N$
$A_1$ $A_2$ $\dots$ $A_N$

출력
현재부터 일본에 육지가 없어질 때까지의 기간(현재 포함) 동안 섬의 개수의 최댓값을 $1$줄로 출력하시오.

소과제

1. ($7$점) $N \le 2000$, $A_i \le 2000$ ($1 \le i \le N$)
2. ($8$점) $N \le 2000$
3. ($85$점) 추가 제약 조건이 없다.

입출력 예제

입력 예제 1

6
0 1 2 1 3 2

출력 예제 1

2

• 해수면의 높이가 $0$ 이상 $1$ 미만일 때, 구획 $2, 3, 4, 5, 6$이 육지이다. 영역 $[2, 6]$이 유일한 섬이므로 섬의 개수는 $1$이다.
• 해수면의 높이가 $1$ 이상 $2$ 미만일 때, 구획 $3, 5, 6$이 육지이다. 영역 $[3, 3]$과 영역 $[5, 6]$이 섬이므로 섬의 개수는 $2$이다.
• 해수면의 높이가 $2$ 이상 $3$ 미만일 때, 구획 $5$만이 육지이다. 영역 $[5, 5]$가 유일한 섬이므로 섬의 개수는 $1$이다.
• 해수면의 높이가 $3$이 되면 육지가 없어지고 섬의 개수는 $0$이 된다.

따라서 섬의 개수의 최댓값은 $2$이므로 $2$를 출력한다.

입력 예제 2

6
3 2 3 0 2 0

출력 예제 2

2

• 해수면의 높이가 $0$ 이상 $2$ 미만일 때, 구획 $1, 2, 3, 5$가 육지이다. 영역 $[1, 3]$과 영역 $[5, 5]$가 섬이므로 섬의 개수는 $2$이다.
• 해수면의 높이가 $2$ 이상 $3$ 미만일 때, 구획 $1, 3$이 육지이다. 영역 $[1, 1]$과 영역 $[3, 3]$이 섬이므로 섬의 개수는 $2$이다.
• 해수면의 높이가 $3$이 되면 육지가 없어지고 섬의 개수는 $0$이 된다.

따라서 섬의 개수의 최댓값은 $2$이므로 $2$를 출력한다.

입력 예제 3

10
4 1 2 1 2 3 5 4 3 2

출력 예제 3

3