일본 열도는 가늘고 긴 열도이다. 열도는 평행한 경계선으로 \(N\)개 구역으로 나뉜다. 구역에는 끝에서부터 \(1\)부터 \(N\)까지 번호가 붙어 있다. 구역 \(i\) (\(1 \le i \le N\))의 높이는 \(A_i\)이다. 열도는 바다에 둘러싸여 있고, 해수면 높이는 장소에 관계없이 같다. 높이가 해수면보다 높은 구역을 육지라 한다. 육지가 이어진 부분을 섬이라 한다. 더 정확히 쓰면 다음과 같다. 정수 \(l\), \(r\) (\(1 \le l \le r \le N\))에 대해, 구역 \(l\), 구역 \(l+1\), \(\ldots\), 구역 \(r\)로 이루어진 부분을 구간 \([l, r]\)이라 한다. 다음을 모두 만족하는 구간 \([l, r]\)을 섬이라 한다.
해수면이 올라가 열도는 조금씩 가라앉고 있다. 지금 해수면 높이는 \(0\)이지만, 시간이 지나면 점점 올라가 마침내는 일본 전체가 바다가 된다. JOI 군은 해수면이 올라가면 섬의 수가 늘거나 줄어든다는 것을 알아차렸다. 지금부터 일본에 육지가 없어질 때까지(지금을 포함) 섬의 수의 최댓값을 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
- 첫째 줄에 구역의 수 \(N\)이 주어진다.
- 둘째 줄에 \(N\)개의 정수 \(A_1, A_2, \ldots, A_N\)이 공백 하나로 구분되어 주어진다.
- \(1 \le N \le 100000\)
- \(0 \le A_i \le 1000000000\)
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 지금부터 일본에 육지가 없어질 때까지(지금을 포함) 섬의 수의 최댓값을 출력한다.
해수면이 \(0\) 이상 \(1\) 미만이면 구역 \(2, 3, 4, 5, 6\)이 육지이고 섬은 구간 \([2, 6]\) 하나이다. 해수면이 \(1\) 이상 \(2\) 미만이면 구역 \(3, 5, 6\)이 육지이고 섬은 \([3, 3]\)과 \([5, 6]\) 둘이다. 해수면이 \(2\) 이상 \(3\) 미만이면 구역 \(5\)만 육지이다. 해수면이 \(3\)이 되면 육지가 없다. 따라서 최댓값은 \(2\)이다.
해수면이 \(0\) 이상 \(2\) 미만이면 구역 \(1, 2, 3, 5\)가 육지이고 섬은 \([1, 3]\)과 \([5, 5]\)이다. 해수면이 \(2\) 이상 \(3\) 미만이면 구역 \(1, 3\)이 육지이고 섬은 \([1, 1]\)과 \([3, 3]\)이다. 해수면이 \(3\)이 되면 육지가 없다. 최댓값은 \(2\)이다.