There are n vertical silo walls standing in a row, wall i having non-negative integer height h[i] and unit width. After a rainstorm, water settles above each wall position, rising up to the smaller of the tallest wall to its left and the tallest wall to its right (water cannot rise above the row's outer boundary). Compute the TOTAL volume of water trapped across the entire row.
Input format
Line 1: an integer n.
Line 2: n space-separated non-negative integers, the wall heights.
Output format
A single integer: the total volume of water trapped.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ h[i] ≤ 100000