Description：

给 $n$ 个数，可以删掉一些数使得尽量多的 $a[i]$ 在 $a[i]$ 位置。

$1\leqslant n\leqslant 10^5$

Solution：

一看就发现和最长上升子序列非常像，列一下转移就是： $$ f[i]=\max(f[j]+1)(j<i,a[j]<a[i],a[i]-a[j]\leqslant i-j) $$ 发现他特别像一个三维偏序，但是仔细观察会发现如果 $a[i]-a[j]\leqslant i-j,a[j]<a[i]$ 那么可以推出 $i<j$ ，于是就是一个二维偏序了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct node

{

	int a,b,id;

}s[MAXN];

bool cmp_b(node x,node y)

{

	if(x.b == y.b)return x.a < y.a;

	else return x.b < y.b;

}

int f[MAXN];

#define MAX 1000000

int c[MAX];

int lowbit(int x){return x & (-x);}

void add(int p,int x){for(int i = p;i <= MAX;i += lowbit(i))c[i] = max(c[i],x);return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res = max(res,c[i]);return res;}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&s[i].a);

	for(int i = 1;i <= n;++i)s[i].b = i - s[i].a;

	for(int i = 1;i <= n;++i)s[i].id = i;

	sort(s + 1,s + 1 + n,cmp_b);

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		if(s[i].a - s[i].id > 0)continue;

		f[i] = query(s[i].a - 1) + 1;

		add(s[i].a,f[i]);

		ans = max(ans,f[i]);

	}

	cout << ans << endl;

	return 0;

}