Trapping Rain Water

Given an array of non-negative integers representing the height of the buildings where the width of each bar is 1, compute how much water it is able to trap after raining.

The trapped water at each position is determined by the formula: \(water[i] = \min(\text{leftMax}[i],\, \text{rightMax}[i]) - \text{height}[i]\), summed for all valid indices i.

For example, given heights [0,1,0,2,1,0,1,3,2,1,2,1], the amount of trapped water is 6.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains an integer N representing the number of buildings.
2. The second line contains N space-separated non-negative integers representing the heights of the buildings.

outputFormat

Output a single integer to standard output (stdout), representing the total amount of water that can be trapped.

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

6