\(i+H_i'\) の偶奇は必ず一致する必要があります。

\(i+H_i'\) が全て偶数であるような場合を考えます。

\(\lbrace 1,2,\ldots,N\rbrace\) の部分集合 \(S\) に対し、\(i\in S\) ならば \(H_i=H_i'\) という条件を考えます。この条件を満たす \(S\) に対する \(|S|\) の最大値が問題の答えです。また、この条件は \(i,j\in S\) に対し \(|H_i - H_j| \le |i-j| \) が成り立つことと同値です。

さらに、\(X_i=H_i-i,Y_i=H_i+i\) とすると、\(i,j\in S\) に対し \(X_i < X_j\) ならば \(Y_i \le Y_j\) 、となります。これは \((X_i,Y_i)\) を辞書順にソートした際の \(Y_i\) の広義単調増加列の長さと一致します。広義単調増加列は準線形時間で計算できるため、ソートを含めても準線形時間で問題の答えを求めることができます。

全て奇数である場合も同様に計算することができます。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

from bisect import bisect_right


def lis(a):
    d = []
    for v in a:
        i = bisect_right(d, v)
        if i == len(d):
            d.append(v)
        else:
            d[i] = v
    return len(d)


n = int(input())
h = list(map(int, input().split()))
a = []
b = []
for i, x in enumerate(h):
    p = (i - x, i + x)
    if (i + x) % 2:
        a.append(p)
    else:
        b.append(p)


def calc(arr):
    arr.sort()
    e = [x for _, x in arr]
    return lis(e)


print(max(calc(a), calc(b)))