지구 온난화

한 과학자가 해수면 상승이 지형을, 그중에서도 섬의 개수를 어떻게 바꾸는지 연구하려고 한다. 먼저 1차원 세계를 살펴본다. 1차원 세계는 음이 아닌 정수 수열 $\langle h_0, h_1, \ldots, h_{n-1} \rangle$로 나타내고, $h_i$는 위치 $i$의 고도이다. 아래 그림은 수열 $\langle 5, 6, 1, 3, 2, 9, 8 \rangle$이 나타내는 세계이다.

해수면이 고도 $2.5$에 있으면 섬이 3개 생긴다. 앞의 두 칸, 네 번째 칸, 마지막 두 칸이 각각 섬을 이룬다. 해수면이 고도 $3.5$에 있으면 섬은 2개뿐이다. 해수면이 고도 $x$일 때 고도가 $x$인 땅은 물에 잠긴 것으로 본다. 그래서 해수면이 고도 $3$일 때도 섬은 2개다. 이 세계에서는 3개가 모든 해수면을 통틀어 가장 많은 섬의 개수이다.

해수면의 높이 $x$는 임의의 실수이고, 섬은 물에 잠기지 않은 칸이 가로로 이어진 최대 구간이다. 1차원 세계가 주어지면 모든 해수면에 대해 섬이 최대 몇 개까지 생기는지 구하라.

프로그램은 표준 입력에서 읽는다. 첫째 줄에 수열에 들어 있는 정수의 개수 $n$이 주어진다. 이어지는 $n$개의 줄에는 각 줄마다 정수가 하나씩 주어지며, 이 $n$개의 수가 수열 $\langle h_0, h_1, \ldots, h_{n-1} \rangle$이다. 수열의 모든 수는 음이 아니고 $2^{30}$보다 작다.

프로그램은 표준 출력에 섬의 최대 개수를 정수 하나로 출력한다.