Trapping Rain Water

Given a list of non-negative integers representing the heights of blocks, compute the total amount of water that can be trapped after a rainfall. The water stored at index \(i\) is determined by the formula: \(w_i = \min(l_{\max}, r_{\max}) - h_i\), where \(l_{\max}\) and \(r_{\max}\) denote the maximum height to the left and right of index \(i\), respectively. Your task is to implement an algorithm to calculate the sum of water stored over all indices.

inputFormat

The input is provided via stdin. The first line contains an integer \(n\) which is the number of blocks. The second line contains \(n\) space-separated non-negative integers representing the heights of the blocks. If \(n = 0\), the list of heights will be empty.

outputFormat

Output a single integer to stdout representing the total amount of trapped water.

5
3 0 2 0 4

7