Trapping Rain Water

You are given an array of non-negative integers, where each integer represents the height of a bar in a histogram. Imagine that it rains: water is trapped between the bars. Your task is to calculate how much water can be trapped after raining.

For each bar at position i, the water that can be trapped on top of it is determined by the formula:

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

where:

• \(\text{leftMax}[i]\) is the maximum height of a bar to the left of index i (inclusive).
• \(\text{rightMax}[i]\) is the maximum height of a bar to the right of index i (inclusive).

Your solution should read the input from standard input (stdin) and output the result to standard output (stdout).

Note: If there are no bars or the configuration does not trap any water, output 0.

inputFormat

The input starts with an integer n (\(0 \leq n \leq 10^5\)) representing the number of bars. The next line contains n space-separated non-negative integers, each representing the height of a bar.

For example:

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

outputFormat

Output a single integer, the total amount of trapped rainwater.

## sample

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

6