Trapping Rain Water

You are given a list of non-negative integers, where each integer represents the height of a wall. Consider that it rains over these walls. You need to calculate how much water is trapped between the walls after the rain. The amount of water that can be trapped on top of a wall is determined by the formula:

\(water[i] = \min(\text{max}_{left},\text{max}_{right}) - height[i]\)

where \(\text{max}_{left}\) is the maximum height to the left of the wall at position i and \(\text{max}_{right}\) is the maximum height to the right. If this difference is negative, consider it as zero water for that position.

Your task is to compute the total water trapped after it rains.

inputFormat

The input is given via stdin in the following format:

1. The first line provides an integer n, representing the number of walls.
2. The second line contains n space-separated non-negative integers representing the heights of the walls.

outputFormat

Output via stdout a single integer, which is the total amount of water that can be trapped between the walls.

6
4 2 0 3 2 5

9