Trapping Rain Water

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

For each index \(i\), the water trapped above it is calculated as \(\min(L_i, R_i) - h_i\), where \(L_i = \max_{0 \leq j \leq i} h_j\) and \(R_i = \max_{i \leq j < n} h_j\). The total trapped water is the sum over all indices.

This is a classic problem that can be solved efficiently using precomputed arrays of left maximums and right maximums.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\) representing the number of buildings. The second line contains \(n\) space-separated non-negative integers where the \(i\)th integer represents the height of the \(i\)th building.

outputFormat

Output a single integer to standard output (stdout) representing the total amount of trapped rain water.

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

6