Trap Rain Water

Given an array of non-negative integers representing the heights of buildings, compute how much rainwater can be trapped after it rains. For each building at position \(i\), the maximum height to its left is denoted by \(left\_max[i]\) and the maximum height to its right is \(right\_max[i]\). The water trapped above building \(i\) is given by \(\min(left\_max[i],right\_max[i]) - \text{height}[i]\) (if positive).

Your task is to implement a program that reads the number of buildings and their heights from standard input and outputs the total trapped rainwater to standard output.

inputFormat

The first line contains an integer \(n\) representing the number of buildings. The second line contains \(n\) space-separated non-negative integers representing the heights of the buildings.

outputFormat

A single integer representing the total amount of trapped rainwater.

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

6