Overview

Among all intervals \((l,r)\) where the sum of absolute differences in elevation between adjacent points (total elevation change) is at least \(K\), we want to minimize the number of included points \(r-l+1\).

Analysis

Key Observation

The total elevation change of route \((l,r)\) is $\(\sum_{i=l}^{r-1} |A_{i+1}-A_i|\)\( which is exactly the range sum of the "adjacent difference" array \)\(B_i = |A_{i+1}-A_i|\quad (1 \le i \le N-1)\)\( namely \)\(\sum_{i=l}^{r-1} B_i\)$

In other words, the problem can be rephrased as:

• Given a non-negative array \(B\) of length \(N-1\)
• Find the length of the shortest contiguous subarray whose sum is at least \(K\)

If the shortest length found is \(m\) (this is the number of edges), then the number of points is one more than the number of edges, so the answer is \(m+1\).

Why a Naive Solution Doesn’t Work

Trying all \((l,r)\) pairs gives \(O(N^2)\) intervals, and computing the total elevation change for each interval naively is clearly too slow (\(N \le 2\times 10^5\)).

Even if we use prefix sums to compute range sums in \(O(1)\), enumerating all intervals itself is \(O(N^2)\), resulting in TLE.

How to Solve It

The decisive property is that \(B_i \ge 0\) (since they are absolute values, they are always non-negative).
For a non-negative array, the “shortest subarray with sum at least a given value” can be found in \(O(N)\) using the two pointers / sliding window technique.

Algorithm

1. Compute \(B[i] = |A[i+1]-A[i]|\) (\(i=0..N-2\)).
2. Use the two pointers technique to maintain the sum \(s\) of the interval \([left, right]\) (an interval on \(B\)).
   • Extend right from 0 onward, adding to \(s\).
   • When \(s \ge K\), the condition is satisfied, so record the length right-left+1 as a candidate answer, then try to shorten further by advancing left (subtracting from \(s\)).
3. The minimum number of edges is obtained as ans. The number of points is ans + 1.
4. If \(s \ge K\) is never achieved, it is impossible, so output -1.

(Example) For \(A = [1, 4, 2, 7]\),
\(B = [|4-1|, |2-4|, |7-2|] = [3,2,5]\).
If \(K=6\), the interval \([2,3]\) (\(2+5=7\)) is the shortest with length 2 (2 edges) → the number of points is 3.

Complexity

• Time complexity: \(O(N)\) (both left and right advance at most \(N\) times each)
• Space complexity: \(O(N)\) (to store the difference array \(B\))

Implementation Notes

• The answer is the “number of points,” not the “number of edges,” so be careful to add +1 at the end.

• \(K\) can be up to \(10^{18}\), so the sum s must be handled with 64-bit integers (in Python this is automatic).

• When \(N=1\), there are no edges and the total elevation change is always 0, so under the constraint \(K \ge 1\), the answer is always -1.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:]

    if N <= 1:
        print(-1)
        return

    B = [abs(A[i+1] - A[i]) for i in range(N - 1)]

    left = 0
    s = 0
    ans = 10**30
    for right, v in enumerate(B):
        s += v
        while s >= K:
            ans = min(ans, right - left + 1)
            s -= B[left]
            left += 1

    if ans == 10**30:
        print(-1)
    else:
        print(ans + 1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.