Trapping Rain Water

Given an array of non-negative integers representing the heights of buildings, your task is to compute how much water can be trapped after it rains. The water above a building is determined by the formula below:

$$ water[i] = \min(\text{left_max}[i],\,\text{right_max}[i]) - height[i] $$

where \(\text{left_max}[i]\) is the maximum height of a building to the left of index \(i\) (inclusive) and \(\text{right_max}[i]\) is the maximum height to the right of index \(i\) (inclusive). The total trapped water is the sum of \(water[i]\) for all indices \(i\). For cases where there are fewer than 3 buildings, no water can be trapped.

inputFormat

A single line containing space-separated non-negative integers representing the heights of the buildings. If the input is empty, it should be treated as an empty list.

outputFormat

Print a single integer representing the total amount of water that is trapped.## sample

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

6