Trapping Rain Water

Given a list of non-negative integers representing the elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The water trapped at any position is determined by the formula:

\( water[i] = \min(\text{left}_{max}[i],\, \text{right}_{max}[i]) - height[i] \)

where \( \text{left}_{max}[i] \) is the maximum height to the left of index \( i \) (inclusive) and \( \text{right}_{max}[i] \) is the maximum height to the right of index \( i \) (inclusive). Your program should read the input from standard input and write the output to standard output.

inputFormat

The first line contains an integer \( N \) which represents the number of elements in the elevation map.

The second line contains \( N \) space-separated non-negative integers where each integer represents the height of the terrain at that position.

outputFormat

Output a single integer representing the total amount of rain water trapped.

0

0