A cross-section of a city block is described by n walls in a row, each of width 1 and a given non-negative integer height. After a monsoon downpour, water is trapped in the dips between taller walls. The water held above any position equals the smaller of the tallest wall to its left and the tallest wall to its right, minus that position's own height (never negative).
Compute the total number of units of water trapped across the whole row.
Input format
Line 1: an integer n.
Line 2: n space-separated non-negative integers, the wall heights left to right.
Output format
A single integer: the total units of trapped water.
Constraints
- 1 <= n <= 100000
- 0 <= height <= 1000000000