Summary

Given a sequence of mountain elevations, we want to find the maximum length of a contiguous subarray that is “mountain-shaped” (strictly increasing then strictly decreasing) such that the difference between the maximum and minimum values is at least \(K\).

The key is to look at the signs of the differences between adjacent elevations and partition the sequence into maximal mountain-shaped intervals in a single pass.

Analysis

An interval \([l, r]\) is mountain-shaped if the changes in adjacent elevations are:

• Initially increasing
• Decreasing from some point onwards
• Note that strictly increasing only or strictly decreasing only is also allowed.

In other words, looking at the signs of the differences between adjacent elements:

• A sequence of \(+\) followed by a sequence of \(-\) is OK (valid).
• A \(+\) appearing after a \(-\) is NG (invalid).
• \(0\) (i.e., equal adjacent elevations) is NG (invalid).

For example, if the elevation sequence is

\[ 1, 3, 5, 4, 2 \]

then the signs of the differences are

\[ +, +, -, - \]

which is mountain-shaped.

On the other hand,

\[ 5, 3, 2, 4 \]

has the signs of differences

\[ -, -, + \]

which decreases and then increases, so it is not mountain-shaped.

---

A naive search of all intervals \([l, r]\) would require checking \(O(N^2)\) intervals.
Since \(N \leq 10^6\), this will easily TLE (Time Limit Exceeded).

Therefore, we construct the maximal contiguous mountain-shaped intervals from left to right.

The key observation is as follows:

If an entire interval is mountain-shaped and the difference between its maximum and minimum values is at least \(K\), then this entire interval is a candidate for the answer.

Moreover, choosing a sub-interval of it would only decrease the length.
Therefore, it is sufficient to check if

\[ \max - \min \geq K \]

holds for each maximal mountain-shaped interval.

---

A mountain-shaped interval is broken in the following two cases:

1. Adjacent elevations are equal

Since the definition of mountain-shaped uses strict inequalities, any interval containing

\[ H_i = H_{i+1} \]

cannot be mountain-shaped.

Thus, we completely split the interval here.

2. Increasing after decreasing

A place where the sign of the difference changes from

\[ - \to + \]

is a valley.

For example,

\[ 5, 3, 4 \]

is

\[ 5 > 3 < 4 \]

so it is not mountain-shaped.

In this case, the previous mountain-shaped interval ends at the valley.
However, since we can start a new increasing sequence from the valley, the next interval starts at this valley.

Algorithm

We scan the elevation sequence from left to right.

For the current mountain-shaped interval, we maintain the following:

• start: The starting position of the current mountain-shaped interval
• seg_min: The minimum elevation in the current interval
• seg_max: The maximum elevation in the current interval
• prev_sign: The sign of the previous difference
  • \(+1\) for increasing
  • \(-1\) for decreasing
  • \(0\) if there is no difference yet

We look at the adjacent elevations \(a = H_i\) and \(b = H_{i+1}\) to find the sign of the current difference curr.

When curr == 0

Since the elevations are equal, the mountain-shaped interval is broken here.

If the current interval satisfies

\[ seg\_max - seg\_min \geq K \]

we update the answer.

Then, we start a new interval from \(H_{i+1}\).

When prev_sign == -1 and curr == 1

Since it increases after decreasing, a valley is formed.

This is not mountain-shaped, so we end the current interval at the valley.

After evaluating the current interval, we start a new interval from the valley.

Otherwise

We can extend the current mountain-shaped interval.

We update seg_min and seg_max and proceed to the next element.

Finally, do not forget to evaluate the last interval after the scan is complete.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(1)\)

Excluding the input array, we only need a constant number of variables during the scan.

Implementation Details

• If adjacent elevations are equal, they cannot be included in the same mountain-shaped interval, so we completely split the interval.

• When transitioning from decreasing to increasing, the valley point becomes the starting point of the new interval.

  • Example: \(5, 3, 4\)
  • The previous interval is \(5, 3\)
  • The next interval is \(3, 4\)

• If \(N = 1\), the difference between the maximum and minimum in the interval is \(0\). Since the constraints guarantee \(K \geq 1\), the answer is always \(0\).

• Since the last interval is not finalized inside the loop, make sure to evaluate it after the loop ends.

  Source Code

import sys

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

    if N <= 1:
        print(0)
        return

    h_prev = data[2]
    start = 0
    seg_min = h_prev
    seg_max = h_prev
    prev_sign = 0
    ans = 0

    idx = 3
    for i in range(N - 1):
        b = data[idx]
        idx += 1
        a = h_prev

        if b > a:
            curr = 1
        elif b < a:
            curr = -1
        else:
            curr = 0

        if curr == 0:
            if seg_max - seg_min >= K:
                length = i - start + 1
                if length > ans:
                    ans = length
            start = i + 1
            seg_min = b
            seg_max = b
            prev_sign = 0
            h_prev = b
            continue

        if prev_sign == -1 and curr == 1:
            if seg_max - seg_min >= K:
                length = i - start + 1
                if length > ans:
                    ans = length
            start = i
            seg_min = a
            seg_max = a

        if b < seg_min:
            seg_min = b
        elif b > seg_max:
            seg_max = b

        prev_sign = curr
        h_prev = b

    if seg_max - seg_min >= K:
        length = N - start
        if length > ans:
            ans = length

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.