Trapping Rain Water

You are given a histogram represented by a sequence of non-negative integers where each integer corresponds to the height of a bar. The width of each bar is 1. Your task is to calculate the total amount of rain water that can be trapped between the bars after it rains.

The water trapped at each bar is determined by the height of the tallest bars to its left and right. Formally, for the i-th bar, the water trapped is given by $$\text{water}_i = \min(L_i, R_i) - \text{height}_i,$$ where L_i is the maximum height among the bars to the left of the i-th bar, and R_i is the maximum height among the bars to the right of the i-th bar. If the above value is negative, then no water is trapped above that bar.

Your solution must read from standard input and write to standard output.

inputFormat

The first line of input contains a single integer n which denotes the number of bars in the histogram. If n is 0, then the histogram is empty.

If n > 0, the second line contains n space-separated non-negative integers where each integer represents the height of a bar.

outputFormat

Output a single integer that represents the total amount of rain water trapped between the bars.

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

6