Trapping Rain Water

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

\[ water_i = \min(L_i, R_i) - h_i \]

where \(L_i\) is the maximum height to the left of index \(i\), \(R_i\) is the maximum height to the right of index \(i\), and \(h_i\) is the height at index \(i\). If the result is negative, treat it as zero.

inputFormat

The input is read from standard input. The first line contains an integer (n) representing 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 to standard output: the total amount of water trapped.## sample

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

6