Exposition

Observation 1: this is a subarray with a window constraint

We need a contiguous segment $[l,r]$ such that

$$\max_{i\in[l,r]} h_i - \min_{i\in[l,r]} h_i \le k,$$

and among all such segments we want the maximum length $r-l+1$, then all segments achieving that length.

So yes, this is a sliding-window problem. The only real question is: how do we maintain window minimum and maximum fast enough?

Observation 2: two pointers works because validity is monotone

Suppose a window $[l,r]$ is valid. Then every subwindow inside it is also valid, because removing elements cannot increase the range $\max-\min.$

That means for each fixed right endpoint $r$, there is a smallest left endpoint $l$ such that $[l,r]$ is valid. If we increase $r$, this $l$ never moves left. Classic two-pointers territory.

So the plan is:

• move $r$ from left to right,
• add $h_r$ into the current window,
• while the window is invalid, move $l$ right,
• after that, $[l,r]$ is the longest valid segment ending at $r$.

The last sentence is the key aha.

Observation 3: maintaining min and max with monotonic deques

If you use a multiset, you get $O(n\log n)$ and it passes. But we can do better and cleaner with two deques:

• mx: indices of elements in decreasing height order, so the front is the maximum.
• mn: indices of elements in increasing height order, so the front is the minimum.

When adding index $r$:

• while mx.back() has height $\le h_r$, pop it, then push $r$;
• while mn.back() has height $\ge h_r$, pop it, then push $r$.

When moving $l$ right:

• if mx.front() == l, pop it;
• if mn.front() == l, pop it.

Then the current window range is simply

$$h_{mx.front()} - h_{mn.front()}.$$

That’s $O(1)$ amortized per operation, because each index enters and leaves each deque once. Beautiful, brutal, effective.

Why storing only the current $[l,r]$ is enough

After we finish shrinking for a fixed $r$, the window $[l,r]$ is valid and minimal in $l$. Therefore it is the longest valid segment ending at $r$.

Its length is

$$len = r-l+1.$$

Now suppose some optimal answer is a segment $[x,r]$ of maximum length best. Since $[l,r]$ is the longest valid segment ending at $r$, we have

$$r-l+1 \ge r-x+1 = best.$$

But best is the global maximum possible length, so actually equality must hold, hence $l=x$.

So every optimal segment appears exactly as the current window for its right endpoint. No need to enumerate shorter valid subwindows or do any weird nonsense.

Algorithm

Initialize:

• $l=0$
• two empty deques mx, mn
• best = 0
• empty answer list

For each $r=0,1,\dots,n-1$:

1. Insert $r$ into both monotonic deques.
2. While $$h_{mx.front()} - h_{mn.front()} > k,$$ move $l$ right by one, removing expired indices from deque fronts.
3. Now the window $[l,r]$ is valid. Let $$len = r-l+1.$$
4. If $len > best$, set best = len, clear the answer list, and store $(l+1,r+1)$.
5. If $len = best$, append $(l+1,r+1)$.

We print 1-based indices because Codeforces would absolutely love to WA you for that.

Correctness sketch

We maintain the invariant that after processing each $r$:

• both deques contain exactly indices inside the current window $[l,r]$,
• mx.front() is the index of the maximum in the window,
• mn.front() is the index of the minimum in the window,
• the window is valid,
• and $l$ is the smallest possible left endpoint making $[l,r]$ valid.

Thus $[l,r]$ is the longest valid segment ending at $r$.

Taking the maximum over all $r$ gives the global optimum. Storing all windows whose length equals that optimum gives exactly the required periods.

No holes, no handwaving, no sacrificial goats.

Complexity

Each index is pushed and popped from each deque at most once.

So the total complexity is

$$O(n),$$

with memory

$$O(n)$$

for the answer list in the worst case (plus $O(n)$ input, $O(n)$ deques in total).

That is comfortably within the limits.