Trapping Rainwater

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, your task is to compute how much water it can trap after raining.

The water trapped at index \(i\) is given by:

\(w_i = \min(\max_{left}(i), \max_{right}(i)) - height[i]\),

where \(\max_{left}(i)\) is the maximum height to the left of index \(i\) (including \(i\) itself) and \(\max_{right}(i)\) is the maximum height to the right of index \(i\) (including \(i\) itself). The total trapped water is the sum of \(w_i\) for all indices.

Please write a program that reads the elevation map from standard input and outputs the total amount of trapped rainwater to standard output.

inputFormat

The first line contains an integer \(n\), which is the number of elements in the elevation map.

The second line contains \(n\) space-separated non-negative integers representing the heights.

outputFormat

Output a single integer representing the total units of trapped rainwater.

## sample

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

6

</p>