Trapping Rain Water

Given a list of non-negative integers representing the heights of walls, compute the total amount of water that can be trapped after rainfall. The water trapped above a wall is determined by the minimum of the maximum heights to its left and right minus the height of the wall. In mathematical terms, for each wall at index \(i\):

\[ \text{water}_i = \max\left(0, \min(\text{leftMax}_i,\, \text{rightMax}_i) - \text{height}_i \right) \]

The task is to sum the water trapped above all the walls.

Example: For the input array [0,1,0,2,1,0,1,3,2,1,2,1], the output is 6.

inputFormat

The first line contains an integer (n), the number of walls. The second line contains (n) non-negative integers separated by spaces, where each integer represents the height of a wall. For example:

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

outputFormat

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

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

6