Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The trapped water is determined by the heights of the bars, and water can only be trapped if there is a higher bar on both sides.

The water trapped above any bar is given by the formula: \( \text{water} = \max(0, \min(\text{left_max},\,\text{right_max}) - h) \), where \(h\) is the height of the current bar, and \(\text{left_max}\) and \(\text{right_max}\) are the maximum heights to the left and right of the bar respectively.

Your task is to compute the total amount of trapped water for the given elevation map.

inputFormat

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

1. The first line contains a single integer n representing the number of terrain columns.
2. The second line contains n space-separated non-negative integers denoting the heights of the terrain.

outputFormat

Output a single integer to standard output (stdout) representing the total amount of water that can be trapped.

## sample

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

6

</p>