Trapping Rain Water

You are given an array 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 that can be trapped at index \(i\) is determined by the height of the tallest bar to its left and right. Formally, if we define \(L_i = \max_{0 \leq j \leq i} \{height[j]\}\) and \(R_i = \max_{i \leq j < n} \{height[j]\}\), then the water trapped at index \(i\) is given by:

[ w_i = \max(0, \min(L_i, R_i) - height[i]) ]

Your task is to calculate \(\sum_{i=0}^{n-1} w_i\), the total amount of trapped water.

inputFormat

The input is given via stdin in the following format:

The first line contains an integer \(n\), the number of elements in the array.
The second line contains \(n\) space-separated non-negative integers representing the heights of the bars.

If \(n = 0\), the second line will be empty.

outputFormat

Output a single integer via stdout which is the total amount of water that can be trapped.

0

0