A row of n garden walls of width 1 stands side by side; wall i has height h[i]. After heavy rain, water collects in the dips between taller walls.
Print the total units of water held.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ h[i] ≤ 100000
Input and output
- Input
- Line 1: n. Line 2: n non-negative integers (the heights).
- Output
- One integer: total trapped water.
Examples
Input 1
5
3 0 2 0 4Output
7Water sits 3, 1 and 3 units deep over the three low bars: 7.
Input 2
4
1 2 3 4Output
0Heights only rise, so nothing is trapped.
Show hints
- Water above wall i = min(tallest on the left, tallest on the right) − h[i].
- With two pointers, the side with the smaller maximum decides how much water stands at that pointer.
Show the explanation
Each position holds min(leftMax, rightMax) − h[i] water. Instead of precomputing both arrays, move two pointers inwards and keep leftMax and rightMax. Whichever side has the smaller maximum is the limiting wall, so the water at that pointer is known now: add max − h and step it inwards. One pass, O(1) extra space.
Original UniCircle question. Last reviewed 22 Oct 2026.