너비가 \(1\)로 모두 같은 막대 \(N\)개가 일렬로 세워져 있고, \(i\)번째 막대의 높이는 \(h_i\)이다. 이 위로 비가 내려 막대 사이의 오목한 곳에 물이 고인다.

각 칸 \(i\)에 고이는 물의 높이는 왼쪽에서 가장 높은 막대 높이 \(\left(\max_{j \le i} h_j\right)\)와 오른쪽에서 가장 높은 막대 높이 \(\left(\max_{j \ge i} h_j\right)\) 중 더 작은 값에서 자기 자신의 높이 \(h_i\)를 뺀 만큼이다 (음수이면 \(0\)).

모든 칸에 고이는 물의 양의 총합을 구하여라.

\(1 \le N \le 100\,000\), \(0 \le h_i \le 10^9\).

첫째 줄에 막대의 개수 \(N\)이 주어진다.

둘째 줄에 \(N\)개의 정수 \(h_1, h_2, \dots, h_N\)이 공백으로 구분되어 주어진다.

고이는 물의 총량을 한 줄에 출력한다.

riseoj 작성

출처 Original