Overview

Given the elevations of \(N\) points, the problem asks us to find the length (number of points) of the longest contiguous interval where the elevations of adjacent points maintain a “previous point \(\leq\) next point” relationship (non-decreasing order).

Analysis

What we want to find in this problem is “the longest interval where the elevation never decreases.”

For example, consider elevations arranged as [1, 2, 5, 3, 4]. - From point 1 to 3, the elevations increase as 1 $\leq$ 2 $\leq$ 5, so this is an ascending slope of length 3. - Moving from point 3 to 4, the elevation drops as 5 > 3, so the ascending slope is interrupted here. - From point 4 to 5, the elevations increase as 3 $\leq$ 4, so this is an ascending slope of length 2. The maximum among these is length 3.

In this way, we can look at the elevations in order from the beginning and count “how far the current ascending slope continues.”

Why we don’t need to check all intervals

If we tried to check all combinations of \(l\) (start point) and \(r\) (end point), the number of combinations would be approximately \(N^2 / 2\). For \(N = 10^5\), this would require about 5 billion computations, which cannot finish within the time limit. However, the moment the elevation decreases, the “ascending slope up to that point” is finalized, and the next ascending slope can be counted starting fresh from “the point after the decrease.” Therefore, we can solve this by scanning the array just once from the beginning (\(O(N)\)).

Algorithm

1. Initialize a variable current_len to hold the current ascending slope length to 1, and a variable max_len to hold the maximum length so far to 1.
2. Compare point \(i\) and point \(i+1\) in order from \(i = 1\) to \(N-1\).
   • If \(A_i \leq A_{i+1}\), the ascending slope continues, so increment current_len by 1.
   • If \(A_i > A_{i+1}\), the ascending slope has been interrupted.
     • Compare the current current_len with max_len, and update max_len with the larger value.
     • Reset current_len to 1 (the start of a new ascending slope).
3. After examining all points, update max_len once more to account for the possibility that the last ascending slope is the longest.
4. Output max_len.

Complexity

• Time complexity: \(O(N)\)
  • Since we scan the list only once from beginning to end, the computation finishes in time proportional to the number of points \(N\).
• Space complexity: \(O(N)\)
  • This is used to store the \(N\) input elevations in a list.

Implementation Notes

• Boundary condition handling: When \(N=1\), the loop is not executed, but since the initial value is 1, the correct output of 1 is produced.

• Update after the loop: If the elevation keeps increasing all the way to the end, the else branch (reset processing) inside the loop is never reached. Therefore, it is necessary to perform the max_len update once more immediately after the loop ends.

• Fast input: When handling input of scale \(N=10^5\) in Python, reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input(), reducing execution time.

  Source Code

import sys

def main():
    # 入力を一括で取得し、分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    # a_1 から a_n までの標高をリストに格納
    a = list(map(int, input_data[1:]))
    
    # 地点が1つしかない場合は、登り坂の長さは1
    if n == 1:
        print(1)
        return
    
    max_len = 1
    current_len = 1
    
    # 隣り合う地点の標高を比較し、広義単調増加（非減少）であるかを確認
    for i in range(n - 1):
        if a[i] <= a[i+1]:
            current_len += 1
        else:
            # 増加が途切れたら、現在の長さを最大値と比較しリセット
            if current_len > max_len:
                max_len = current_len
            current_len = 1
            
    # 最後の区間の長さを確認
    if current_len > max_len:
        max_len = current_len
        
    print(max_len)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-thinking.