Trapping Rain Water

Given an elevation map represented by an array of non-negative integers, each element indicates the height of a bar. When it rains, water is trapped between these bars. Your task is to compute the total amount of water that can be trapped.

The water trapped at index \(i\) can be calculated using the formula:

\[ \text{water}[i] = \min\big(\max_{0 \leq j \leq i} \text{height}[j],\; \max_{i \leq j < n} \text{height}[j]\big) - \text{height}[i] \]

Sum this value for all indices \(i\) (taking zero if the difference is negative) to determine the total trapped water.

inputFormat

The input is read from standard input and consists of two parts:

• The first line contains an integer \(n\) representing the number of bars.
• If \(n > 0\), the second line contains \(n\) space-separated non-negative integers representing the heights of the bars. If \(n == 0\), there is no second line.

outputFormat

Output a single integer to standard output representing the total volume of water that can be trapped.

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

6