Taco's Maximum Water Trapped

Given an array of non-negative integers where each integer represents the elevation of a bar, compute the maximum amount of water that can be trapped after it rains. The amount of water that can be trapped at each position is determined by the formula (water_i = \max(\min(left_{max},, right_{max}) - height[i],, 0)), where (left_{max}) is the maximum height to the left of position (i) and (right_{max}) is the maximum height to the right of position (i).

inputFormat

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

outputFormat

Output a single integer that represents the maximum amount of water trapped between the bars.## sample

11
1 0 2 1 0 1 3 2 1 2 1

6