Overview

The post-maintenance elevation sequence that satisfies the condition is a “mountain path” where adjacent elevations must change by exactly \(1\). We want to choose a subset of checkpoints to keep at their original elevations, convert the condition of whether this subset is simultaneously realizable into a manageable form, and find the maximum number of checkpoints we can keep.

Analysis

First, let’s consider keeping both of two checkpoints \(i < j\) as they are.
To match the code, we will assume 0-indexed positions.

Letting their elevations be \(H_i\) and \(H_j\), there are \(j-i\) steps between \(i\) and \(j\).
Since the difference between adjacent elevations must be exactly \(1\), the conditions for being able to reach \(H_j\) from \(H_i\) in \(j-i\) steps are the following two:

1. The difference in height is at most the number of steps:
   $\( |H_i - H_j| \le j-i \)$

2. The parities match:
   Since we perform \(\pm 1\) a total of \(j-i\) times, the parity of the height flips with each step.
   Therefore, $\( (i + H_i) \bmod 2 = (j + H_j) \bmod 2 \)$

Here, we apply the following transformation:

\[ x_i = i + H_i \]

\[ y_i = i - H_i \]

Then, the condition \(|H_i - H_j| \le j-i\) can be decomposed into the following two:

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

This is

\[ i + H_i \le j + H_j \]

which means

\[ x_i \le x_j \]

Also,

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

This is

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

which means

\[ y_i \le y_j \]

Therefore, when looking only at points with the same parity, the checkpoints we can keep form a sequence that satisfies both \(x_i \le x_j\) and \(y_i \le y_j\), which is a monotonically increasing sequence in 2D space.

---

A naive search of “which checkpoints to keep” would take \(2^N\) combinations, which is far too slow.
Also, DP with elevations as states is impossible since \(H_i \le 10^9\).

Thus, we can convert each checkpoint to \((x_i, y_i)\), divide them by parity, and find the “Longest Non-Decreasing Subsequence (LNDS) of \(y\) when sorted in ascending order of \(x\)”.

Here, it is important that the subsequence is “non-decreasing”.
If \(y\) is equal, the condition \(y_i \le y_j\) is still satisfied, so they can be kept simultaneously.

Algorithm

1. For each checkpoint \(i\), compute the following:

$\( x = i + H_i \)$

$\( y = i - H_i \)$

1. Divide them into two groups based on the parity of \(x\), i.e., \((i + H_i) \bmod 2\).

2. For each group, sort the points \((x, y)\) in ascending order of \(x\).

3. Find the Longest Non-Decreasing Subsequence (LNDS) for the sorted sequence of \(y\).

In Python, you can find the non-decreasing subsequence by using bisect_right.

   pos = bisect_right(tails, v)

tails[k] represents “the minimum possible value of the end of a non-decreasing subsequence of length \(k+1\)”.

1. The maximum of the LNDS lengths of the two parity groups is the answer.

Complexity

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

Implementation Points

• The position \(i\) is treated as 0-indexed in the code using enumerate(H).

• Checkpoints with different \((i + H_i) \bmod 2\) cannot be kept at the same time, so they must be separated into different groups.

• Since the condition is \(y_i \le y_j\), we need the LNDS (Longest Non-Decreasing Subsequence) instead of the LIS (Longest Increasing Subsequence). Therefore, we use bisect_right instead of bisect_left.

• \(y = i - H_i\) can be negative, but this is not an issue since it is only used for sorting and comparison.

  Source Code

import sys
from bisect import bisect_right

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

    groups = [[], []]
    for i, h in enumerate(H):
        groups[(i + h) & 1].append((i + h, i - h))

    ans = 0
    for g in groups:
        g.sort()
        tails = []
        for _, v in g:
            pos = bisect_right(tails, v)
            if pos == len(tails):
                tails.append(v)
            else:
                tails[pos] = v
        ans = max(ans, len(tails))

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.