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 integer n, representing the number of bars in elevation map

The second line contains n integers, representing the height of each bar in the elevation map

Output

Print an integer which is how much water it can trap after raining.

Example

Input

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

Output

6

Explanation

The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.