Stretches With a Total in Range

A small shop records its profit for each day, and changes[i] is the profit on day i (negative on a day that lost money). A stretch is one or more consecutive days. Write count_in_range(changes, low, high) that returns how many stretches have a total profit between low and high, both included.

Examples

count_in_range([3, -2, 4], 1, 3)       # returns 3
count_in_range([5, 5, 5], 10, 10)      # returns 2
count_in_range([2, -2, 2, -2], 0, 0)   # returns 4

In the first example the six stretches have totals 3, -2, 4, 1, 2 and 5, and three of them (3, 1 and 2) are between 1 and 3.

Constraints

• 0 <= len(changes) <= 30,000
• -10^5 <= changes[i] <= 10^5
• -10^9 <= low <= high <= 10^9

Note

30,000 days have about 450 million stretches, far too many to add up one by one.