Trapping Rain Water

Given an array of non-negative integers representing the heights of bars in a histogram, compute how much water can be trapped after raining. Each bar has a width of 1.

The water trapped above the bar at index i can be computed using the formula:

$$ W_i = \min(L_i, R_i) - h_i $$

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 water above each bar.

This problem simulates how water is trapped between walls of various heights.

inputFormat

The input consists of two lines. The first line contains a positive integer n, denoting the number of bars in the histogram. The second line contains n non-negative integers, separated by spaces, representing the heights of the bars.

outputFormat

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

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

6