Maximum Latency Drift Windows

A network reliability engineer is reviewing a sequence of n latency-delta readings captured back to back from a monitoring probe. Reading i records how much the round-trip latency changed since the previous probe: a positive value means latency got worse by that many milliseconds, a negative value means it improved, and the readings are given in the fixed order they were captured.

The engineer wants to flag the largest possible number of non-overlapping (index-disjoint) contiguous runs of consecutive readings such that the deltas within each flagged run add up to exactly a given target drift value. Flagged runs never need to touch or cover every reading — any number of unflagged readings may sit between, before, or after them — but no two flagged runs may share a reading, and no reading may be reused across runs.

Determine the maximum number of such non-overlapping runs that can be flagged.

Input format

• Line 1: an integer n — the number of readings.
• Line 2: an integer target — the required delta sum for a flagged run.
• Line 3: n space-separated integers — the latency deltas in probe order.

Output format

A single integer: the maximum number of non-overlapping contiguous runs whose deltas sum exactly to target.

Constraints

• 1 <= n <= 100000
• -10000 <= reading[i] <= 10000
• 0 <= target <= 1000000

5
2
1 1 1 1 1

2

6
2
-2 4 -2 4 -2 4

3