Trapped Rain Water

You are given an array of non-negative integers representing the heights of columns. Imagine that the width of each column is 1. After it rains, water is trapped between the columns. Your task is to compute how much water is trapped.

The amount of water that can be trapped on top of a column at index i is given by:

[ water[i] = \min(\text{leftMax}[i],,\text{rightMax}[i]) - height[i] ]

where:

• leftMax[i] is the maximum height of the columns to the left of i (inclusive).
• rightMax[i] is the maximum height of the columns to the right of i (inclusive).

Return the total water trapped across all columns.

Note: If the number of columns is 2 or less, no water can be trapped.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains a single integer n representing the number of columns.
• The second line contains n space-separated integers representing the heights of the columns.

Example:

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

outputFormat

The output is written to stdout and consists of a single integer on a line representing the total volume of water trapped.

Example:

6

## sample

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

6

</p>