Trapping Rain Water

Given an array \(A\) of non-negative integers representing an elevation map where the width of each bar is \(1\), your task is to compute how much water it is able to trap after raining. The water trapped at position \(i\) can be computed as:

[ w_i = \max\left(0, \min\left(L_i, R_i\right) - A[i]\right) ]

where \(L_i\) is the maximum height to the left of index \(i\) and \(R_i\) is the maximum height to the right of index \(i\). The total trapped water is the sum of \(w_i\) over all positions \(i\).

It is guaranteed that the input contains at least one bar.

inputFormat

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

1. The first line contains a single integer \(n\) denoting the number of bars.
2. The second line contains \(n\) non-negative integers separated by spaces representing the heights of the bars.

outputFormat

Output a single integer to standard output (stdout) which is the total amount of trapped rain water.

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

6