Trapping Rain Water on Cubes

Given a sequence of non-negative integers, each representing the height of a stack of cubes (a pillar) where each stack has a height \(x\) because there are \(x\) cubes (with \(0 \le x \le 5000\)), compute the total area where water can be trapped. Water can accumulate in the gaps between pillars when there exists a higher pillar on both sides. The water trapped over a pillar at index \(i\) is computed by:

\[ \text{water}(i) = \max\Big(0, \min(\text{maxLeft},\,\text{maxRight}) - h[i]\Big), \]

where \(\text{maxLeft}\) is the maximum height to the left of \(i\) (including \(i\)) and \(\text{maxRight}\) is the maximum height to the right of \(i\) (including \(i\)). The task is to output the total water trapped (i.e. the sum of water trapped over all indices). Each unit in the water is considered as an area of 1.

inputFormat

The input consists of two lines.

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)) representing the number of pillars.
• The second line contains \(n\) space-separated non-negative integers, each representing the height of a pillar.

Note: Each height \(x\) satisfies \(0 \le x \le 5000\).

outputFormat

Output a single integer which denotes the total area (in unit area) of water that can be trapped between the pillars.

sample

10
0 1 0 2 1 2 0 0 2 0

6