Trapping Rain Water

Given $n$ non-negative integers representing an elevation map where the width of each bar is $1$.

Compute how much water it can trap after raining.

Input

The first line contains the value of $n(n\le 10^5)$.

The second line contains $n$ non-negative integers $h_1,h_2,...,h_n(h_i\le 10^5)$.

Output

Print how much water can be trapped after raining.

Examples