파일 업로드

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

 

물놀이를 좋아하는 지훈은 비가 오면 항상 마당에 물이 차오른다는 것을 발견했습니다. 그런데 마당이 완벽하게 평평하지 않기 때문에 물은 균일하게 차오르지 않고, 물에 잠기지 않은 '섬'들을 남기게 됩니다.

지훈의 마당은 1차원적인 풍경으로 N (1 <= N <= 100,000)개의 연속적인 높이 값 H(1)...H(n)으로 설명됩니다. 이 풍경이 높은 울타리에 둘러싸여 있을 때, 비가 내릴 때 어떤 일이 일어나는지 생각해봅시다: 가장 낮은 지역부터 물로 덮여지면서 여러 개의 분리된 "섬"을 형성하게 됩니다. 이 섬들은 물이 계속 높아짐에 따라 결국 모두 덮여질 것입니다. 물의 높이가 땅의 높이와 동일해지는 순간, 그 땅은 물에 잠긴 것으로 간주됩니다.

예를 들어, 왼쪽에 표시된 것처럼 1단위 이상의 물을 추가하면 4개의 섬(이 게임에서 볼 수 있는 최대 수)이 남게 됩니다. 물 총 7단위를 추가한 후에는 오른쪽 그림과 같이 두 개의 섬만이 노출됩니다. 비가 내릴 때 전체 마당이 물에 잠길 때까지 한 번에 보이는 섬의 최대 개수를 계산해주세요.

💻 입력
  • 1번째 줄: 정수 N.
  • 2번째 줄..1+N번째 줄 :  i+1번째 줄은 높이 H(i)를 담고 있습니다. (1 <= H(i) <= 1,000,000,000)
🖨️ 출력
  • 1번째 줄: 비가 내리는 동안 한 번에 나타나는 섬의 최대 개수를 나타내는 한 개의 정수.

💻 예제 입력 1
8
3
5
2
3
1
4
2
3
🖨️ 예제 출력 1
4

출처: USACO 2012 US Open, Bronze Division Problem 3. Islands