刚刚ABC G,WA一个点求调

#include <bits/stdc++.h>

using namespace std;

int n;
int a[200010], b[200010];
int f[200010], g[200010];
map<int, int> ma; int id;
map<int, int> Id;
pair<int, int> c[200010];

void add(int x, int d, int id) {
	for (; x <= n; x += (x & -x)) {
		if (d > c[x].first) {
			c[x].first = d;
			c[x].second = id;
		} else if (d == c[x].first && id > c[x].second) {
			c[x].first = d;
			c[x].second = id;
		}
	}
}

pair<int, int> query(int u) {
	pair<int, int> res = {0, 0};
	for (; u; u -= (u & -u)) {
		if (c[u].first > res.first) {
			res = c[u];
		} else if (c[u].first == res.first && c[u].second > res.second) {
			res = c[u];
		}
	}
	return res;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), b[i] = a[i];
	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; ++i) {
		if (!ma.count(b[i]))
			ma[b[i]] = ++id;
	}

	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		auto t = query(ma[a[i]] - 1);
		f[i] = t.first + 1;
		g[i] = i;
		// cout << t.first << ' ' << t.second << endl;
		if (t.first) {
			g[i] = t.second;
		}
		add(ma[a[i]], f[i], i);
		ans = max(ans, f[i]);

	}

	for (int i = 1; i <= n; ++i) {
		if (f[i] == ans && i != n) {
			printf("%d\n", f[i] + 1);
			return 0;
		}
	}

	vector<int> p;
	int u = n;
	p.push_back(n);
	while (g[u] != u) {
		u = g[u];
		p.push_back(u);
	}

	if (p.back() != 1) {
		printf("%d\n", ans + 1);
		return 0;
	}

	for (int i = p.size() - 1; i >= 1; --i) {
		// cout << p[i] << ' ' << p[i];
		if (p[i] + 1 < p[i - 1] && a[p[i]] + 1 < a[p[i - 1]]) {
			printf("%d\n", ans + 1);
			return 0;
		}
	}

	printf("%d\n", ans);

	return 0;
}