# Trapping Rain Water

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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≤10_{5})$.

The second line contains $n$ non-negative integers $h_{1},h_{2},...,h_{n}(h_{i}≤10_{5})$.

## Output

Print how much water can be trapped after raining.

## Examples

Input #1

Answer #1

Input #2

Answer #2

Submissions 302

Acceptance rate 49%