Rainwater in the Ruins

Difficulty: 1700 3000 ms 128 MB

two-pointers

Walls of the given heights stand in a row (width 1 each). After rain, how much water is trapped between them?

Input: the first line has N; the second line has N non-negative heights.

Output: the total trapped water.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ h_i ≤ 10⁹

Sample Tests

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

6

2
5 5

0

Read the Editorial