Trapping Rain Water

Problem statement

A miniature roof has adjacent columns, each one unit wide. After rain, water remains in dips bounded by taller columns on both sides. Calculate the total units of trapped water. Water beyond either end drains away.

Input format

First line: n. Second line: n space-separated integers.

Output format

Print the total trapped water.

Constraints

1 <= n <= 100000; 0 <= height <= 1000000000; use 64-bit arithmetic.

Sample input

6
4 1 0 2 1 4

Sample output

12