Trapping Rain Water

Hard#arrays #two-pointers #stack· solved by 0 · time limit 2.0 s

Bars of width 1 have heights $h_1 \dots h_n$ . After rain, how much water is trapped between them?

Input

$n$ , then $n$ heights.

Units of trapped water.

$1 \le n \le 2 \times 10^5$ , $0 \le h_i \le 10^5$

Input

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

Output

Input

6
4 2 0 3 2 5

Output