Trapping Rain Water

You are given an array representing the heights of towers. When it rains, water is trapped between the towers. Your task is to compute how much water is trapped after raining.

For each index i, the water trapped is determined by the formula:

$$ water_i = \min(L_i, R_i) - h_i $$

where:

• \(h_i\) is the height at index \(i\),
• \(L_i\) is the maximum height among the towers to the left of \(i\) (including \(i\) itself),
• \(R_i\) is the maximum height among the towers to the right of \(i\) (including \(i\) itself).

The total trapped water is the sum of \(water_i\) for all indices.

Note that if there is no tower to one side, the water trapped at that index is 0.

inputFormat

The input is given in two lines:

• The first line contains an integer \(n\) denoting the number of towers.
• If \(n > 0\), the second line contains \(n\) space-separated non-negative integers representing the heights of the towers.

If \(n = 0\), the second line will be empty.

outputFormat

Output a single integer which is the total amount of trapped water.

## sample

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

6

</p>