Trapping Rain Water

This problem is known as Trapping Rain Water. You are given an array of non-negative integers where each integer represents the height of a bar. Imagine it rains and water collects between the bars. Your task is to compute the total amount of water that can be trapped.

The water trapped at a position i can be computed as:

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

where \( \max_{left}(i) \) is the maximum height to the left of index i (inclusive) and \( \max_{right}(i) \) is the maximum height to the right of index i (inclusive). If the result is negative, treat it as zero.

Make sure your implementation reads input from standard input and writes the result to standard output.

inputFormat

The first line contains an integer n, representing the number of bars. The second line contains n non-negative integers separated by spaces, representing the heights of the bars.

outputFormat

Output a single integer which is the total amount of water that can be trapped.## sample

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

6