Trapping Rainwater

Given a list of non-negative integers representing the heights of buildings, compute the total units of rainwater that can be trapped between these buildings after rainfall.

The water trapped at position \(i\) can be computed using the formula:

\( water[i] = \min(left\_max[i], right\_max[i]) - height[i] \),

where \( left\_max[i] \) is the highest building on the left of position \(i\) (inclusive) and \( right\_max[i] \) is the highest on the right of position \(i\) (inclusive).

This is a classical problem that can be solved in \(O(N)\) time using dynamic programming by precomputing the \( left\_max \) and \( right\_max \) arrays.

inputFormat

The input begins with an integer \(N\) denoting the number of buildings. The next line contains \(N\) space-separated non-negative integers representing the heights of the buildings.

outputFormat

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

## sample

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

6

</p>