Rain Collector

After a storm, water settles between the flat-roofed buildings of a city block. Each building is one unit wide; water trapped above a spot is bounded by the tallest building to its left and the tallest to its right.

Given the building heights, compute the total amount of trapped rain water.

Input

The first line contains one integer n — the number of buildings.

The second line contains n integers h₁ … hₙ — the heights.

Output

Print the total units of trapped water.

Constraints

• 1 ≤ n ≤ 2·10⁴
• 0 ≤ hᵢ ≤ 10⁷

12
0 1 0 2 1 0 1 3 2 1 2 1

6

5
3 0 0 0 3

9