Stretches Reaching the Goal

steps[i] is the (non-negative) number of steps walked on day i. Count the non-empty contiguous stretches of days whose total is at least goal.

Examples

Input:  steps = [1, 2, 3], goal = 3
Output: 4
Explanation: [1, 2], [3], [2, 3] and [1, 2, 3] reach 3; [1] and [2] do not.

Input:  steps = [0, 0, 0], goal = 1
Output: 0

Constraints

• 1 <= len(steps) <= 10**5
• 0 <= steps[i] <= 10**4, 1 <= goal <= 10**9
• Target complexity: O(n log n) or O(n). Enumerating every stretch is too slow for the largest tests.

Goals

• Exploit that non-negative values make prefix totals non-decreasing
• Count qualifying start positions with bisect instead of a loop