Trapping Rain Water

You are given an elevation map represented by n non-negative integers, where each integer corresponds to the height of a bar and the width of each bar is 1. Your task is to compute how much water can be trapped after it rains.

Mathematically, let (h[i]) be the height of the bar at index (i), and let (L(i) = \max_{0 \leq j \leq i} h[j]) and (R(i) = \max_{i \leq j < n} h[j]). Then, the water trapped at index (i) is given by:

[ w[i] = \max(0, \min(L(i), R(i)) - h[i]) ]

The total trapped water is the sum of (w[i]) over all indices (i).

inputFormat

The input consists of two lines:

1. The first line contains a single integer (n), the number of bars.
2. The second line contains (n) space-separated non-negative integers representing the heights of the bars.

outputFormat

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

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

6