Water Trapping between Reservoirs

Given a list of non-negative integers representing the height of reservoirs, compute the total amount of water that can be trapped after it rains. The water at each index (i) is determined by ( water_i = \min(leftMax_i, rightMax_i) - height_i ), where ( leftMax_i ) is the maximum height to the left of index (i) and ( rightMax_i ) is the maximum height to the right. There are multiple datasets provided; for each dataset, output the total water trapped.

inputFormat

The input consists of multiple lines. Each line (except the last) represents a dataset and contains space-separated non-negative integers describing the heights of reservoirs. The last line contains a single 0 indicating the end of input.

outputFormat

For each dataset, output a single integer on a new line representing the total amount of water trapped.## sample

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

6
7
0