일본 침몰

문제

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

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

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

• 구획 $l$, 구획 $l+1$, $...$, 구획 $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$)

서브태스크

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

입력과 출력

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

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

예제 입력 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