Trapped Water Calculation

Given an array of non-negative integers representing an elevation map where the width of each bar is 1 unit, compute the total amount of water that can be trapped after raining.

The water trapped above each bar is defined as:

\( water[i] = \min(\text{max}_{\text{left}}(i),\; \text{max}_{\text{right}}(i)) - height[i] \)

where \( \text{max}_{\text{left}}(i) \) is the maximum height to the left of index \( i \) (inclusive), and \( \text{max}_{\text{right}}(i) \) is the maximum height to the right of index \( i \) (inclusive). If the computed water amount is negative, treat it as zero.

Your task is to write a program that reads the elevation map from standard input and outputs the total water trapped.

Example: For the elevation map [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the output should be 6.

inputFormat

The first line contains a single integer \( n \) representing the number of bars in the elevation map. The second line contains \( n \) space-separated non-negative integers that denote the height of each bar.

outputFormat

Output a single integer, which is the total units of water trapped.

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

6