Trapping Rain Water

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For each index (i), the water trapped is determined by (\min(L_i, R_i) - h_i), where (L_i) and (R_i) are the maximum heights to the left and right of index (i) (inclusive), respectively. Your task is to calculate the total amount of trapped water.

inputFormat

The first line contains an integer (n), the number of elements in the elevation map. The second line contains (n) space-separated non-negative integers representing the heights.

outputFormat

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

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

6