Overview

In this problem, we are given a sequence \(H\). We want to construct a sequence \(H'\) such that the absolute difference between adjacent elements is exactly \(1\), and all elements are non-negative integers. We want to find the maximum number of elements we can keep from the original sequence (i.e., \(H_i = H'_i\)).

By formulating the conditions mathematically, this problem can be reduced to the Longest Increasing Subsequence (LIS) problem, which can be solved efficiently.

---

Observation

1. Condition to Keep Two Checkpoints Intact

Let’s consider the condition under which the elevations \(H_i\) and \(H_j\) of two checkpoints \(i\) and \(j\) (\(i < j\)) can be kept intact without modification.

Since the elevation difference between adjacent checkpoints is exactly \(1\), the elevation can change by at most \(1\) for each step forward. Therefore, during the transition from position \(i\) to \(j\), the change in elevation must be at most the difference in indices, \(j - i\). That is, the following inequality must hold:

\[|H_j - H_i| \le j - i\]

We can remove the absolute value and rewrite this as:

1. \(H_j - H_i \le j - i \iff i - H_i \le j - H_j\)
2. \(-(H_j - H_i) \le j - i \iff i + H_i \le j + H_j\)

Here, we define the following two values for each \(i\): - \(x_i = i - H_i\) - \(y_i = i + H_i\)

Then, the condition to keep the original elevations can be rephrased as: for \(i < j\), both \(x_i \le x_j\) and \(y_i \le y_j\) must hold.

2. Parity Condition

Furthermore, since the difference between adjacent elevations is exactly \(1\), the parity of the elevation must alternate with each step. This means that for all \(i\), the parity of \(i + H'_i\) must be the same.

Therefore, all checkpoints whose original elevations are kept must have the same parity of \(i - H_i\) (or \(i + H_i\)).

3. Reduction of the Problem

Based on the above observations, we can break down the problem as follows:

1. Divide each checkpoint into two groups, the even group and the odd group, based on the parity of \(x_i = i - H_i\).
2. For each group, find the maximum number of checkpoints we can keep such that the condition “\(x_i \le x_j\) and \(y_i \le y_j\) for \(i < j\)” is satisfied.
3. The answer is the maximum of the values obtained from the two groups.

Within each group, we first sort the elements in ascending order of \(x_i\) (and in ascending order of \(y_i\) if \(x_i\) is equal). Once sorted, finding the length of a subsequence where the values of \(y_i\) are non-decreasing—specifically, the Longest Non-Decreasing Subsequence—gives the maximum number of checkpoints we can keep in that group.

Note: The condition that the elevations must be non-negative (\(H'_i \ge 0\)) is always achievable. As long as the parities match and the conditions above are satisfied, we can always interpolate between the kept checkpoints such that the elevation never drops below \(0\) (for example, by bouncing between \(0\) and \(1\) if necessary).

---

Algorithm

1. Initialization and Grouping For each \(i = 1, 2, \ldots, N\), compute \(x_i = i - H_i\) and \(y_i = i + H_i\). Based on the parity of \(x_i\), assign the coordinate pair \((x_i, y_i)\) to either the list g0 (even) or g1 (odd).

2. Sorting Sort g0 and g1 in ascending order. This automatically orders them by \(x_i\) in ascending order (and by \(y_i\) in ascending order in case of ties).

3. Calculating the Longest Increasing Subsequence (LIS) Extract only the \(y_i\) values from each sorted group to form an array, and apply a fast LIS algorithm using binary search. Since we need a non-decreasing (weakly increasing) subsequence that allows duplicate values, we use bisect_right for the binary search.

4. Outputting the Answer Output the maximum of the LIS length obtained from g0 and the LIS length obtained from g1.

---

Complexity

• Time Complexity: \(O(N \log N)\)

  • Grouping takes \(O(N)\).
  • Sorting takes \(O(N \log N)\).
  • Calculating the LIS using binary search takes \(O(N \log N)\).
  • Overall, the time complexity is \(O(N \log N)\), which is fast enough for \(N \le 2 \times 10^5\).

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

  • We use \(O(N)\) memory to store the arrays for each group and the DP array for the LIS calculation.

---

Implementation Details

• Converting to 1-indexed Since the checkpoints in the problem statement are indexed from \(1\) to \(N\), we need to treat the index of the \(i\)-th element (0-indexed in code) as i + 1 during implementation.

• Handling Non-Decreasing Subsequences For a standard LIS (strictly increasing), we would use bisect_left for binary search. However, in this problem, we can keep multiple elements even if they have the same \(y_i\) value (since their \(x_i\) values will be different). To allow equal values and find the non-decreasing subsequence, we use bisect_right instead.

  Source Code

import sys
from bisect import bisect_right

def solve_lis(arr):
    dp = []
    for x in arr:
        idx = bisect_right(dp, x)
        if idx == len(dp):
            dp.append(x)
        else:
            dp[idx] = x
    return len(dp)

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    H = [int(x) for x in data[1:]]
    
    g0 = []
    g1 = []
    
    for i in range(N):
        h = H[i]
        idx = i + 1
        x = idx - h
        y = idx + h
        if x % 2 == 0:
            g0.append((x, y))
        else:
            g1.append((x, y))
            
    g0.sort()
    g1.sort()
    
    y0 = [p[1] for p in g0]
    y1 = [p[1] for p in g1]
    
    ans0 = solve_lis(y0)
    ans1 = solve_lis(y1)
    
    print(max(ans0, ans1))

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3.5-flash-high.