Trapping Rain Water

You are given a list of non-negative integers representing the heights of walls, where the width of each wall is 1. Your task is to compute how much water can be trapped after it rains.

The water trapped at any position is determined by the minimum of the highest wall to its left and the highest wall to its right minus the height at that position. Formally, for an array heights of length n, the water trapped is computed as:

$$\text{Water} = \sum_{i=0}^{n-1} \max\left(0, \min(\text{leftMax}_i, \; \text{rightMax}_i) - \text{heights}_i\right)$$

where:

• $$\text{leftMax}_i = \max(\text{heights}_0,\, \text{heights}_1,\, \ldots, \text{heights}_i)$$
• $$\text{rightMax}_i = \max(\text{heights}_i,\, \text{heights}_{i+1},\, \ldots, \text{heights}_{n-1})$$

Your solution should read the input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

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

outputFormat

Output a single integer representing the total amount of water that can be trapped.

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

6