Trapping Rain Water

You are given an elevation map represented by an array of non-negative integers, where each integer represents the height of a bar. The width of each bar is 1. After it rains, water will be trapped between the bars. Your task is to calculate the total amount of water that can be trapped.

The water trapped above the bar at index \(i\) is determined by the minimum of the highest bar on its left and the highest bar on its right minus the height at index \(i\), if that difference is positive. Mathematically, the water trapped at index \(i\) is given by:

$$ water[i] = \max\Big(0, \min\Big(\max_{0 \leq j < i} A[j],\; \max_{i < j < n} A[j]\Big) - A[i]\Big) $$

Compute the total water trapped over all bars.

inputFormat

The first line contains an integer (n), the number of bars. The second line contains (n) space-separated non-negative integers representing the elevation of each bar.

outputFormat

Output a single integer representing the total units of trapped water.## sample

6
0 1 0 2 1 0

1