Trapping Rain Water

You are given an array of non-negative integers representing the elevation of bars where the width of each bar is 1. Compute how much water is trapped after it rains.

The water above each bar i is determined by the formula:

\( w_i = \min(L_i, R_i) - h_i \)

where \(L_i\) is the maximum height of a bar to the left of index \(i\) (including \(i\)) and \(R_i\) is the maximum height to the right of index \(i\) (including \(i\)). The total trapped water is the sum of water trapped on all bars.

inputFormat

The input is given in two lines. The first line contains an integer n representing the number of bars. The second line contains n space-separated non-negative integers representing the elevation of each bar.

If n is 0, then no bars are present and the answer is 0.

outputFormat

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

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

6