Problems
Trapping Rain Water
Trapping Rain Water
Given $n$ non-negative integers representing an elevation map where the width of each bar is $1$.
Compute how much water it can trap after raining.
\includegraphics{https://static.eolymp.com/content/hr/hr59vusb896rb7hos1d4ci84q0.gif}
\InputFile
The first line contains the value of $n~(n \le 10^5)$.
The second line contains $n$ non-negative integers $h_1, h_2, ..., h_n~(h_i \le 10^5)$.
\OutputFile
Print how much water can be trapped after raining.
Input example #1
12 0 1 0 2 1 0 1 3 2 1 2 1
Output example #1
6
Input example #2
6 4 2 0 3 2 5
Output example #2
9