842. Save Rain Water

0

Hard

Given the current importance of rainwater harvesting, Ram has started collecting rainwater. He has placed boxes of different heights and width 1 on the ground, and water is collected between two boxes. Ram wants to know the total amount of water stored between the boxes.

Input Format

The first line of input will contain the size of the array. The next line will contain the heights of the boxes.

Output Format

Print a single integer representing the total amount of water trapped.

Example

Input

6
4 2 0 3 2 5

Output

9

Constraints

1 <= n <= 2 * 10

0 <= a[i] <= 10

^{4}0 <= a[i] <= 10

^{5}Loading...

View Submissions

Console