Terrace Rainfall

hard

A hillside farm is cut into a row of stone terraces of varying heights, one unit wide each. When the monsoon comes, rain fills the dips between taller terraces; water that isn't walled in on both sides runs off the ends.

Given terraces where terraces[i] is the height of the i-th terrace, return the total units of water the terraces hold after the rain.

Water above any position rises to min(tallest terrace to its left, tallest to its right) and no higher — minus the stone already there.

Example 1

in terraces = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

out 6

Water pools in the dips: 1 unit over index 2, 1 over index 4, 2 over index 5, 1 over index 6, 1 over index 9.

Example 2

in terraces = [3, 1, 2]

out 1

One unit sits on the height-1 terrace, walled by 3 and 2.

Example 3

in terraces = [1, 2, 3]

out 0

A staircase holds nothing — every drop runs off the low side.

Constraints

· 1 <= len(terraces) <= 2 * 10^5
· 0 <= terraces[i] <= 10^5