Bottles leave a filling machine in a fixed order; fills[i] is the measured fill volume of bottle i. The line packs them into crates by cutting the sequence into contiguous, non-empty groups; every bottle goes into exactly one crate and the order is never changed. A crate passes inspection when the fullest and the emptiest bottle in it differ by at most tolerance, that is max(group) - min(group) <= tolerance.
Return the number of different ways to cut the whole line into crates that all pass inspection, modulo 10**9 + 7. Two ways differ when some cut position differs.
Examples
Input: fills = [4, 6, 5, 9], tolerance = 2
Output: 4
Explanation: 9 must be alone; [4, 6, 5] may be cut anywhere:
[4|6|5|9], [4|6 5|9], [4 6|5|9], [4 6 5|9].
Input: fills = [3, 3, 3], tolerance = 0
Output: 4
Input: fills = [1, 10], tolerance = 5
Output: 1
Constraints
1 <= len(fills) <= 10**5-10**9 <= fills[i] <= 10**9,0 <= tolerance <= 2 * 10**9- Target complexity: O(n). Crates can be very long, so trying every start for every end is too slow.
Goals
- Count partitions of a sequence with a dp over cut positions
- Notice that the earliest allowed start of the last crate only moves right
- Combine two monotonic deques with a prefix sum of the dp table