Trapping Rain Water

Given an array of non-negative integers representing the height of buildings, compute how much rainwater can be trapped between these buildings after a heavy rain.

The water trapped at each position i can be computed with the formula:

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

where left_max[i] is the maximum height to the left of i (inclusive) and right_max[i] is the maximum height to the right of i (inclusive). Your task is to compute the total amount of water trapped.

inputFormat

The input consists of a single line containing space-separated non-negative integers representing the heights of the buildings.

outputFormat

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

4 2 0 3 2 5

9