A hiking trail is a closed loop of n checkpoints. track[i] is the height gain (possibly negative) of the leg that starts at checkpoint i; after the leg at n - 1 the trail returns to checkpoint 0.
A stretch is a run of consecutive legs walked in order, possibly passing from leg n - 1 to leg 0. Stretches of length 1 to n - 1 are identified by their starting leg and length. The whole loop (all n legs) is one single stretch, no matter where you start it.
Return how many stretches have a total height gain of exactly target.
Examples
Input: track = [3, -1, 2, 1], target = 4
Output: 2
Explanation: legs 0..2 give 3 - 1 + 2 = 4, and the wrapping stretch leg 3, leg 0 gives 1 + 3 = 4.
Input: track = [2, 2, 2], target = 4
Output: 3
Explanation: legs (0,1), (1,2) and the wrapping pair (2,0).
Input: track = [1, -1], target = 0
Output: 1
Explanation: only the whole loop, which is counted once.
Constraints
1 <= n <= 10**5-10**4 <= track[i] <= 10**4,-10**9 <= target <= 10**9- Target complexity: O(n). Trying every start and length is far too slow for the largest tests.
Goals
- Split circular stretches into straight ones and ones that wrap past the end
- Count wrapping stretches through their straight complement
- Count the full loop exactly once