Maximum Trapped Rain Water

Given an array of non-negative integers representing the heights of buildings, determine the maximum amount of water (in units) that can be trapped between the buildings after raining.

The water trapped at a position is determined by the minimum of the maximum height to its left and the maximum height to its right minus the height at that position. Formally, if we denote the array by \( arr \) with \( n \) elements, the water trapped at index \( i \) is \( \min(\max_{0 \leq j \leq i} arr[j], \max_{i \leq j < n} arr[j]) - arr[i] \), taken as zero if negative.

This problem requires you to read the input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

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

If \( n \) equals 0, it means there are no buildings.

outputFormat

Output a single integer representing the maximum water units that can be trapped.

8
0 2 0 3 0 4 0 5

9