섬

비가 올 때마다 농부 John의 밭은 물에 잠긴다. 밭이 완벽하게 평평하지 않기 때문에 물은 고르지 않게 차오르고, 물 위로 드러난 땅은 서로 떨어진 여러 개의 "섬"으로 나뉘곤 한다.

밭은 $N$개의 연속된 높이 값 $H_1, H_2, \dots, H_N$으로 주어지는 1차원 지형이다. 밭의 양쪽 끝은 사실상 무한히 높은 벽으로 막혀 있다고 하자. 폭우가 밭을 채우면 가장 낮은 지역부터 물에 잠기면서 여러 개의 분리된 섬이 생기고, 결국에는 모든 땅이 물에 잠긴다. 물의 높이가 어떤 땅의 높이와 같아지는 순간, 그 땅은 물에 잠긴 것으로 본다.

예를 들어 높이가 $3, 5, 2, 3, 1, 4, 2, 3$일 때, 물을 $1$ 단위보다 조금 더 채우면 섬이 $4$개 생기며(이 순간이 섬이 가장 많은 때이다), 물을 모두 합쳐 $7$ 단위만큼 채우면 드러난 섬은 $2$개만 남는다.

물이 전혀 없는 상태에서 시작하여 밭 전체가 물에 잠길 때까지, 어느 한 순간에 동시에 보이는 섬의 최대 개수를 구하여라.

• 첫째 줄에 정수 $N$이 주어진다 ($1 \le N \le 100{,}000$).
• 다음 $N$개의 줄 중 $i$번째 줄에는 높이 $H_i$가 주어진다 ($1 \le H_i \le 1{,}000{,}000{,}000$).

• 폭우가 진행되는 동안 어느 한 순간에 나타나는 섬의 최대 개수를 정수 하나로 출력한다.

높이가 $3, 5, 2, 3, 1, 4, 2, 3$인 경우를 생각해 보자. 물의 높이가 $2$보다 크고 $3$보다 작은 구간에 있을 때, 높이가 $3$ 이상인 칸들만 물 위에 남아 땅을 $4$개의 서로 떨어진 섬으로 나누며, 이것이 어느 순간에 볼 수 있는 섬의 최대 개수이다.