리에투스(비)

면접 대비

시간 제한1초메모리 제한1024 MB

요약

높이가 다른 N개의 기둥이 있을 때, 기둥 사이에 고이는 빗물을 큐브 개수로 구합니다.

난이도: 보통10점 중 4점
유형: 배열, 투 포인터
정답자: 아직 제출이 없습니다

문제

아도마스에게는 너비가 1이고 길이가 $N$ , 높이가 $M$ 인 상자가 있다. 상자에는 단위 정육면체 큐브를 채울 수 있으며, 최대 $N \times M$ 개가 들어갈 수 있다. 다만 $N$ 개의 열 각각에는 $M$ 개보다 적은 큐브를 위로 쌓을 수도 있다.

아도마스는 큐브가 든 상자를 밖에 두고 잊어버렸고, 그 위로 비가 내렸다. 열마다 쌓인 큐브 수가 달라서 일부 열에는 물이 고일 수 있다. 상자의 옆면( $N \times M$ 크기)과 바닥은 빽빽한 재질이라 물이 새지 않는다. 반면 상자의 양 끝면( $1 \times M$ 크기)은 물을 붙잡아 두지 못한다.

그림 1. $N = 6$ , $M = 5$ 이고 비가 그친 뒤 물 세 칸이 남은 모습이다.

떨어지는 물의 양은 무한하다고 가정한다.

비가 그친 뒤 상자에 남은 물의 양을 구하라. 남은 물의 부피는 같은 부피를 차지하는 큐브의 개수로 잰다.

입력

첫 줄에 두 정수 $N$ 과 $M$ 이 주어진다. 이어지는 $N$ 개의 줄에는 각각 해당 열의 높이를 나타내는 정수가 하나씩 주어진다.

출력

남은 물의 부피가 차지하는 큐브의 개수를 정수 하나로 출력한다.

제한

$1 \le N, M \le 1{,}000{,}000$

예제2

예제 1
입력
```
6 5
1
3
2
1
4
2
```
예상 출력
```
3
```
예제 2
입력
```
3 2
2
2
1
```
예상 출력
```
0
```