Maximum Water Trapped

You are given an array of non-negative integers representing the elevation map where the width of each bar is 1. Your task is to calculate how much water can be trapped after raining.

The water trapped between the bars can be computed using the formula:

\( \text{Water at index } i = \min(\text{max height to left of } i, \text{max height to right of } i) - \text{height}[i] \),

if the result is positive. Otherwise, it is 0. Compute the total units of water trapped across the entire elevation map.

Input: The first line contains an integer N, representing the number of elements in the elevation map. The second line contains N space-separated non-negative integers.

Output: Print a single integer representing the maximum units of water that can be trapped.

inputFormat

The input starts with a single integer N (the size of the elevation map). The following line contains N space-separated non-negative integers representing the height of each bar in the elevation map.

For example:

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

outputFormat

Output a single integer which is the total units of water that can be trapped after raining.

For example, for the above input, the output should be:

6

## sample

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

6

</p>