Trapping Rain Water

Given an array of non-negative integers representing an elevation map where the width of each bar is 1 unit, your task is to calculate how much water it can trap after raining. The water trapped at index \(i\) is given by:

\[ w_i = \max\Big(0, \min\Big(\max_{0 \leq j \leq i} h[j],\; \max_{i \leq j \leq n-1} h[j]\Big) - h[i]\Big) \]

where \(h[i]\) is the height of the bar at index \(i\). Sum up \(w_i\) for all indices to obtain the total trapped water.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\) \((0 \leq n \leq 10^5)\) representing the number of bars. If \(n > 0\), the second line contains \(n\) space-separated non-negative integers representing the heights of the bars.

outputFormat

Output a single integer (to stdout) representing the total amount of water trapped.

## sample

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

6

</p>