Rain Water Trapping

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute the total amount of water that can be trapped after raining. The water trapped at position ( i ) is given by [ \text{water}_i = \min(\text{left_max}_i,; \text{right_max}_i) - \text{height}_i ] where ( \text{left_max}_i ) is the maximum height to the left of index ( i ) and ( \text{right_max}_i ) is the maximum height to the right of index ( i ). If no water can be trapped, output 0.

inputFormat

The first line of input contains an integer ( n ) representing the number of elevations. The second line contains ( n ) space-separated non-negative integers representing the elevation heights.

outputFormat

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

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

6