Summary

The elevation sequence after maintenance is a sequence where adjacent elements always differ by exactly \(+1\) or \(-1\).
We want to choose as many checkpoints as possible whose current elevations \(H_i\) can be preserved, and consider whether there exists a “path moving up or down by \(1\) at each step” that passes through them.

Analysis

We can think of preserving the elevation \(H_i\) of checkpoint \(i\) as “passing through the point \((i, H_i)\)”.

Let’s consider the condition under which we can preserve two checkpoints \(i < j\) simultaneously.
From \(i\) to \(j\), we can move \(j-i\) times, and the elevation changes by \(+1\) or \(-1\) in each step.

Therefore, the condition to reach \((j, H_j)\) from \((i, H_i)\) is as follows:

• The required elevation difference is within the number of moves.
  \(|H_j - H_i| \le j - i\)
• The parity matches.
  The parities of \((H_j - H_i)\) and \((j-i)\) must match.

Here, we define the following variables:

\(u_i = H_i + i\)

\(v_i = i - H_i\)

Then, for \(i < j\):

\(u_j - u_i = (H_j - H_i) + (j - i)\)

\(v_j - v_i = (j - i) - (H_j - H_i)\)

Therefore, \(|H_j - H_i| \le j-i\) can be rewritten as:

\(u_i \le u_j\) and \(v_i \le v_j\)

Also, the parity condition corresponds to the parities of \(u_i\) being the same.
Indeed, in the sequence after maintenance, the elevation changes by \(1\) at each step, so the parity of \(H'_i + i\) is always constant.

In other words, the checkpoints we can preserve must be chosen such that:

• The parities of \(u_i = H_i + i\) are all the same.
• \(u_i\) is non-decreasing.
• \(v_i\) is non-decreasing.

This reduces to finding the “longest 2D non-decreasing subsequence” for each parity.

A naive DP that checks all pairs would take \(O(N^2)\) time, which is too slow for \(N \le 2 \times 10^5\).
Therefore, after sorting by \(u\), we find the longest non-decreasing subsequence with respect to \(v\).

Algorithm

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

\(u = H_i + i\)

\(v = i - H_i\)

Then, we group the points \((u, v)\) by the parity of \(u\).

For each parity group, we perform the following process:

1. Sort the points in ascending order of \(u\).
   If \(u\) is the same, sort them in ascending order of \(v\).
2. Find the longest non-decreasing subsequence of \(v\) in this order.
3. The length of this subsequence is the maximum number of checkpoints we can preserve for this parity.

Finally, we output the maximum of the answers for the even and odd groups.

The longest non-decreasing subsequence can be found using a dp array, similar to the standard LIS (Longest Increasing Subsequence).

Let dp[k] be “the minimum possible ending value of a non-decreasing subsequence of length \(k+1\)”.

For each \(v\), we search for the first element in dp that is strictly greater than \(v\) using upper_bound.

• If no such element is found, append \(v\) to the end.
• If found, replace that element with \(v\).

Since we are looking for a non-decreasing subsequence, identical values can be used consecutively.
Therefore, we use upper_bound instead of lower_bound.

Complexity

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

Implementation Notes

• Since \(H_i\) can be up to \(10^9\), it is safe to use long long for \(u = H_i + i\) and \(v = i - H_i\).

• \(v\) can be negative.

• To find the longest non-decreasing subsequence, use upper_bound for the binary search.

• In the sequence after maintenance, the parity of \(H'_i + i\) is constant, so we cannot preserve points with different parities at the same time. Thus, we process each parity separately and take the maximum.

  Source Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    array<vector<pair<ll, ll>>, 2> pts;

    for (int i = 1; i <= N; i++) {
        ll h;
        cin >> h;
        ll u = h + i;
        ll v = (ll)i - h;
        pts[u & 1].push_back({u, v});
    }

    auto solve = [](vector<pair<ll, ll>>& a) -> int {
        sort(a.begin(), a.end());

        vector<ll> dp;
        for (auto [u, v] : a) {
            auto it = upper_bound(dp.begin(), dp.end(), v);
            if (it == dp.end()) dp.push_back(v);
            else *it = v;
        }
        return (int)dp.size();
    };

    cout << max(solve(pts[0]), solve(pts[1])) << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.