Lượng nước mưa đọng lại

Buổi 03 — Mảng 1 Chiều two-pointers
Points
26
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho một mảng $H$ gồm $n$ số nguyên không âm biểu diễn độ cao của các cột liền kề có chiều rộng bằng $1$. Sau khi trời mưa, hãy tính tổng lượng nước tối đa có thể đọng lại giữa các cột.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$. Dòng thứ hai chứa $n$ số nguyên không âm $H_1, H_2, \dots, H_n$.

Dữ liệu ra

Một số nguyên duy nhất là tổng lượng nước đọng lại.

Ví dụ

Input

12
0 1 0 2 1 0 1 3 2 1 2 1

Output

6
Giới hạn

$1 \le n \le 2 \cdot 10^5$, $0 \le H_i \le 10^9$.

Draft saved