Define \(d[i][v]\) as the maximum length of a conforming subsequence, that ends with \(v\), of the first \(i\) elements. Then the sought value is the maximum value of \(d[i][v]\).

The transition of this DP (Dynamic Programming) is as follows: \(d[i][v]\) equals \(d[i][v]=\max(d[i-1][v], d[i-1][v-1]+1)\) if \(v=A_i\), and \(d[i][v]=d[i-1][v]\) if \(v\neq A_i\).

We can update \(d[i]\) in-place (reuse the DP array), and actually maintain only non-zero elements in a map while performing DP updates, so that the problem can be solved in \(O(N \log N)\) time.

The problem can be solved by appropriately implementing the algorithm above. For more details, please refer to the sample code.

Sample code (Python3)

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
for v in a:
    d[v] = max(d[v], d[v - 1] + 1)
print(max(d.values()))

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	unordered_map<int, int> d;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int ai;
		cin >> ai;
		d[ai] = max(d[ai], d[ai - 1] + 1);
		ans = max(ans, d[ai]);
	}
	cout << ans << endl;
}