Trapping Rain Water

You are given an array of n non-negative integers which represent the height of pillars. When it rains, water gets trapped between these pillars. Your task is to compute the total units of water that can be trapped.

For each position i, the water above it is determined by the formula:

\( w_i = \max(\min(\text{leftMax}_i,\,\text{rightMax}_i) - height[i],\,0) \)

where \( \text{leftMax}_i \) is the maximum height to the left of index \(i\) and \( \text{rightMax}_i \) is the maximum height to the right of index \(i\). The answer is the sum of water trapped at each index.

Note that if the array length is less than 2, no water can be trapped.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer n representing the number of pillars. The second line contains n space-separated non-negative integers which denote the heights of the pillars.

outputFormat

Output a single integer to standard output (stdout), which represents the total units of water that can be trapped between the pillars.## sample

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

6