Trapping Rain Water

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

For each index i, the water that can be trapped on top of the block is computed using the formula:

\( water[i] = \max\Big( \min(\text{max_left}_i, \text{max_right}_i) - height[i],\ 0 \Big) \)

where max_left_i is the maximum height of a block to the left of index i and max_right_i is the maximum height to the right of index i.

Your task is to compute the total amount of water that can be trapped.

inputFormat

The input is read from the standard input (stdin) and consists of two lines:

1. The first line contains an integer n (0 ≤ n ≤ 10⁵) representing the number of blocks.
2. The second line contains n space-separated non-negative integers representing the elevation map.

outputFormat

Print a single integer to the standard output (stdout) representing the total amount of water that can be trapped.

0

0