Overview

Among “stable” contiguous intervals where the maximum − minimum is at most \(D\), we want to find the longest possible length among those with length at least \(K\).

Analysis

The condition for an interval to be stable is: [ \max(H_l,\dots,H_r)-\min(H_l,\dots,H_r)\le D ] What we want is the maximum length of an interval satisfying this condition (with length \(\ge K\)).

Why a naive solution is too slow

If we try all pairs \((l,r)\), there are \(O(N^2)\) intervals, and computing the max and min for each interval takes additional time, so for \(N\le 5\times 10^5\) this is far too slow.

Key insight

• If we think of a “two-pointer (sliding window)” approach where we extend the right endpoint \(r\) one day at a time, we can advance the left endpoint \(l\) to restore the condition when it breaks.
• However, for this to work, we need to be able to efficiently update the “maximum and minimum of the current interval \([l,r]\)”.
• By using a monotonic queue, we can maintain the max and min in \(O(1)\) (amortized) at each step.

(Example) Even when adding a new value to the interval, by discarding values from the back of the queue that can never be the max (or min) candidate, we can always keep the front of the queue as the maximum (or minimum).

Algorithm

The following is done in 0-indexed fashion.

1. Initialize the left endpoint \(l=0\) and the answer best=0.
2. Extend the right endpoint \(r=0,1,\dots,N-1\) in order (adding \(H_r\) to the interval).
3. Prepare maxdq to manage the maximum of interval \([l,r]\) and mindq to manage the minimum, both storing indices.
   • maxdq is maintained so that the corresponding values \(H\) are monotonically non-increasing (large → small). Tail elements smaller than the value being added \(x=H_r\) can never be the maximum, so pop them.
   • mindq is maintained so that the corresponding values \(H\) are monotonically non-decreasing (small → large). Tail elements larger than the value being added \(x\) can never be the minimum, so pop them.
4. After adding, while the stability condition is violated (\(H[\text{maxdq}[0]]-H[\text{mindq}[0]]>D\)), shrink from the left:
   • If the index at the front of maxdq is exactly \(l\), that element is now outside the interval, so popleft.
   • Do the same for mindq.
   • Advance \(l\) to \(l+1\).
5. At this point, the interval \([l,r]\) is guaranteed to be stable, so update best with the length \(r-l+1\).
6. Finally, if best >= K, output best; otherwise output -1. (We have found the longest stable interval, but if its length is less than \(K\), then no interval satisfying the condition exists.)

Complexity

• Time complexity: \(O(N)\) (Each element enters the deque at most once and leaves at most once, so the total is amortized \(O(N)\).)
• Space complexity: \(O(N)\) (In the worst case, the deque may hold \(N\) indices.)

Implementation Notes

• Store indices, not values in the deque (this makes it easy to determine whether an element has “left the interval” when the left endpoint \(l\) moves).

• Resolving condition violations is done with a while loop (moving \(l\) just once may not be enough if the difference still exceeds \(D\)).

• The final answer is not simply best; a check for best >= K is necessary (output -1 if no valid interval exists).

  Source Code

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K, D = data[0], data[1], data[2]
    H = data[3:3+N]

    maxdq = deque()  # indices, H non-increasing
    mindq = deque()  # indices, H non-decreasing

    l = 0
    best = 0

    for r, x in enumerate(H):
        while maxdq and H[maxdq[-1]] < x:
            maxdq.pop()
        maxdq.append(r)

        while mindq and H[mindq[-1]] > x:
            mindq.pop()
        mindq.append(r)

        while H[maxdq[0]] - H[mindq[0]] > D:
            if maxdq[0] == l:
                maxdq.popleft()
            if mindq[0] == l:
                mindq.popleft()
            l += 1

        if r - l + 1 > best:
            best = r - l + 1

    print(best if best >= K else -1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.