An elevation map is given as n bars of unit width, where bar i has non-negative height h[i]. After heavy rain, water pools in the dips between taller bars. Above each position the water level equals the smaller of the tallest bar to its left and the tallest bar to its right; water trapped there is that level minus the bar's own height (never negative).
Return the total units of trapped water.
Input format
Line 1: an integer n, the number of bars.
Line 2: n space-separated non-negative integers, the bar heights (present whenever n >= 1).
Output format
A single integer: the total units of trapped water.
Constraints
- 1 <= n <= 100000
- 0 <= h[i] <= 1000000