Rain between the walls

Problem

Walls of different heights stand in a row, each one unit wide. After rain, water collects between walls. Print the total number of water units trapped. Use two pointers and O(1) extra space.

Input, output and limits

Input: One line of non-negative wall heights separated by spaces.
Output: One integer: the trapped water.
Constraints: 1 ≤ number of walls ≤ 100000
0 ≤ each height ≤ 100000

Examples

Example 1

Input

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

Output

Six units are trapped.

Example 2

Input

4 2 0 3 2 5

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

Water above a wall is limited by the shorter of the tallest wall on its left and the tallest on its right.

Hint 2

Keep the tallest wall seen from each side. Move the pointer on the side with the smaller tallest wall, because that side decides its water.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems