Trapping Rain Water

You are given a list of non-negative integers representing the heights of bars in a histogram. When it rains, water is trapped between the bars. Your task is to compute how much water can be trapped. The problem can be mathematically formulated as follows:

Given an array \(H = [h_0, h_1, \dots, h_{n-1}]\) where each \(h_i \ge 0\) denotes the height of the bar at index \(i\), determine the total volume of water that can be trapped between the bars after a rain.
More formally, if \(W_i\) denotes the water above bar \(i\), then \[ W_i = \max(0, \min(\max_{j \le i} h_j, \max_{j \ge i} h_j) - h_i) \quad \text{for } i = 0,1,\dots,n-1, \] and you must compute \(\sum_{i=0}^{n-1} W_i\).

Input/Output Details:
You will be given the number of histogram bars followed by the heights of the bars in a single test case. Read the input from stdin and output the maximum water trapped to stdout.

inputFormat

The first line contains an integer n representing the number of histogram bars. The second line contains n space-separated non-negative integers, where the \(i\)th integer represents the height of the \(i\)th bar. If n is 0, the second line may be absent.

outputFormat

Output a single integer representing the maximum volume of water that can be trapped between the histogram bars.

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

6