Trapping Rainwater

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 problem is formulated as follows. Given an array \( h[0..n-1] \) where each element represents the height of a bar, find the total amount of rainwater that can be trapped between the bars. The water trapped at a position \( i \) depends on the maximum height to the left and right of \( i \). Mathematically, the water trapped at index \( i \) is given by:

[ w(i) = \min{ L(i), R(i) } - h[i] ]

where \( L(i) \) is the maximum height to the left of \( i \) (including \( i \)) and \( R(i) \) is the maximum height to the right of \( i \) (including \( i \)). The total trapped water is \( \sum_{i=0}^{n-1} w(i) \), with the convention that if \( w(i) < 0 \), it is treated as 0.

This is a classic problem that challenges one to find an efficient way to compute the water trapped using precomputation of maximum heights from both ends.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer \( n \) representing 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 \), then there will be no second line and the array is considered empty.

outputFormat

Output a single integer on a new line representing the total amount of trapped rainwater, printed via standard output (stdout).

## sample

11
0 1 0 2 1 0 3 1 0 1 2

8

</p>