Trapping Rain Water Problem

Given an array of non-negative integers height representing an elevation map where the width of each bar is 1, compute how much water can be trapped after raining.

You are provided an array of integers where each integer represents the height of a vertical bar at that index. The trapped water at any index i is determined by the following formula:

w_i = \( \min(left\_max[i],\; right\_max[i]) - height[i] \)

where \( left\_max[i] \) is the maximum height to the left of i (including i), and \( right\_max[i] \) is the maximum height to the right of i (including i). Your task is to calculate the total amount of water that can be trapped.

Example 1:

Input: 12
       0 1 0 2 1 0 1 3 2 1 2 1
Output: 6

Example 2:

Input: 6
       4 2 0 3 2 5
Output: 9

inputFormat

The first line contains an integer n representing the number of elements in the elevation array. The second line contains n space-separated integers representing the heights of the bars.

If n = 0, then no further input is provided.

outputFormat

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

## sample

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

6