실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
물놀이를 좋아하는 지훈은 비가 오면 항상 마당에 물이 차오른다는 것을 발견했습니다. 그런데 마당이 완벽하게 평평하지 않기 때문에 물은 균일하게 차오르지 않고, 물에 잠기지 않은 '섬'들을 남기게 됩니다.
지훈의 마당은 1차원적인 풍경으로 N (1 <= N <= 100,000)개의 연속적인 높이 값 H(1)...H(n)으로 설명됩니다. 이 풍경이 높은 울타리에 둘러싸여 있을 때, 비가 내릴 때 어떤 일이 일어나는지 생각해봅시다: 가장 낮은 지역부터 물로 덮여지면서 여러 개의 분리된 "섬"을 형성하게 됩니다. 이 섬들은 물이 계속 높아짐에 따라 결국 모두 덮여질 것입니다. 물의 높이가 땅의 높이와 동일해지는 순간, 그 땅은 물에 잠긴 것으로 간주됩니다.
예를 들어, 왼쪽에 표시된 것처럼 1단위 이상의 물을 추가하면 4개의 섬(이 게임에서 볼 수 있는 최대 수)이 남게 됩니다. 물 총 7단위를 추가한 후에는 오른쪽 그림과 같이 두 개의 섬만이 노출됩니다. 비가 내릴 때 전체 마당이 물에 잠길 때까지 한 번에 보이는 섬의 최대 개수를 계산해주세요.
8 3 5 2 3 1 4 2 3
4