Trapping Rain Water

Given a list of non-negative integers representing the heights of buildings, compute the total amount of water that can be trapped after raining. The water trapped above the i-th building can be computed by:

\( water_i = \max\big(0,\min(\max_{0 \leq j \leq i}{h_j},\,\max_{i \leq j \leq n-1}{h_j}) - h_i \big) \)

Your task is to calculate the total water that accumulates between the buildings.

inputFormat

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

outputFormat

Output a single integer representing the total amount of water trapped.

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

6