Overview

This problem asks you to find the length of the “longest non-decreasing contiguous subsequence (contiguous interval)” in array \(A\), where a contiguous interval continuously satisfies \(A_i \leq A_{i+1}\). It can be solved by scanning from left to right just once, updating the current ascending run length as you go.

Analysis

First, it is important that the “ascending run” must be a contiguous interval. In other words, once the condition \(A_i \leq A_{i+1}\) breaks at some point, you have no choice but to start building a new ascending run from there.

Key Insight

• By comparing the current point \(a\) with the previous point prev:
  • If prev <= a, the current ascending run can be extended
  • Otherwise, the ascending run is broken, so reset the length to 1
• It is sufficient to maintain “the current ascending run length cur_len” and “the maximum so far ans” at each step.

Why the Naive Approach Is Too Slow

For example, if you try extending rightward from each starting point \(l\) to find the longest run, the worst case is \(1 + 2 + \cdots + N = O(N^2)\) Since \(N \le 10^5\), this won’t be fast enough.

Solution

Scan the array from left to right just once, updating cur_len based on the comparison of adjacent pairs of elements. This is fast because each element is processed exactly once.

Algorithm

1. Read \(N\).
2. Read the first elevation as prev.
3. Initialize cur_len = 1, ans = 1.
4. For each of the remaining \(N-1\) elevations a, in order:
   • If prev <= a, then cur_len += 1
   • Otherwise, cur_len = 1
   • ans = max(ans, cur_len)
   • Update prev = a
5. Output ans.

Concrete Example

For \(A = [2, 2, 5, 3, 4, 4]\): - \(2 \to 2\) : extends (cur=2) - \(2 \to 5\) : extends (cur=3) - \(5 \to 3\) : breaks (cur=1) - \(3 \to 4\) : extends (cur=2) - \(4 \to 4\) : extends (cur=3)

The maximum is 3.

Complexity

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

Implementation Notes

• Since the input can be large, it is safer to use sys.stdin.readline.

• When \(N=1\), the initial values cur_len=ans=1 handle it correctly.

• The condition is “non-decreasing (weakly monotonically increasing),” so the comparison should be <=, not <.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    
    prev = int(input().strip())
    cur_len = 1
    ans = 1
    
    for _ in range(1, N):
        a = int(input().strip())
        if prev <= a:
            cur_len += 1
        else:
            cur_len = 1
        if cur_len > ans:
            ans = cur_len
        prev = a
    
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.