Trapping Rain Water

Given an array of non-negative integers representing the heights of buildings where the width of each building is 1 unit, your task is to compute the maximum amount of water that can be trapped after raining. The water trapped above the i-th building is given by the formula:

$W_i = \min(L_i, R_i) - H[i]$,

where:

• $H[i]$ is the height of the i-th building,
• $L_i = \max\{H[0], H[1], \dots, H[i]\}$ is the maximum height to the left of the i-th building (inclusive), and
• $R_i = \max\{H[i], H[i+1], \dots, H[n-1]\}$ is the maximum height to the right of the i-th building (inclusive).

The total water trapped is the sum of water trapped above each building. Your solution should read input from stdin and output the result to stdout.

inputFormat

The first line of input contains a single integer n which represents the number of buildings. The second line contains n space-separated integers representing the heights of the buildings.

If n is 0, there are no buildings and the trapped water is 0.

outputFormat

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

6
0 1 3 0 1 2

3