A road has n segments and segment i must end up with exactly layers[i] layers of asphalt. The paving machine lays one layer on exactly k consecutive segments per pass, and every pass must fit fully on the road. A segment cannot lose layers once they are laid.
Return the smallest number of passes that gives every segment exactly its required number of layers, or -1 if it cannot be done.
Examples
Input: layers = [1, 2, 2, 1], k = 2
Output: 3
Explanation: one pass on segments 0-1, one on 1-2 and one on 2-3.
Input: layers = [2, 3, 1], k = 2
Output: 3
Explanation: two passes on 0-1 leave [2, 2, 0]; one pass on 1-2 gives [2, 3, 1].
Input: layers = [2, 1], k = 3
Output: -1
Explanation: a pass would not fit on a two-segment road.
Constraints
1 <= n <= 10**5,1 <= k <= 10**5(kmay exceedn)0 <= layers[i] <= 10**6- Target complexity: O(n). Adding each pass cell by cell costs about
passes * ksteps, far too slow for the largest tests.
Goals
- See that the leftmost unfinished segment forces the passes that start there
- Track how many passes cover the current segment with a difference array
- Detect overshoot and passes that would run off the road