Trapping Rain Water

Given a list of non-negative integers representing the heights of bars, compute the total amount of rainwater that can be trapped after a rainfall. The water accumulated above each bar is determined by the formula:

$$w_i = \min(\text{left\_max}_i,\; \text{right\_max}_i) - h_i$$

where \(\text{left\_max}_i\) is the maximum height to the left of the \(i^{th}\) bar and \(\text{right\_max}_i\) is the maximum height to the right of the \(i^{th}\) bar, and \(h_i\) is the height of the \(i^{th}\) bar. Your task is to compute the total trapped rainwater.

inputFormat

The first line contains a single integer \(n\) which represents the number of bars. If \(n > 0\), the second line contains \(n\) space-separated non-negative integers representing the heights of the bars. If \(n = 0\), no second line is provided.

outputFormat

Output a single integer representing the total amount of rainwater that can be trapped.

6
4 2 0 3 2 5

9