Part

定义一个长度为 k 的序列 B 是好的当且仅当 \(?1≤i 。

给出序列 A ，求最少能把序列 A 划分成多少个好的子序列（注意：子序列不要求连续）。

（划分的意思就是每个元素都在这些好的子序列中的一个且仅一个中出现过，值相同但是位置不同的元素被视作是不同的）

输入格式
第一行一个整数 n ，表示 A 的长度。

第二行 n 个整数表示 A 。

输出格式
一行一个整数表示最少能把序列 A 划分成多少个好的子序列。

样例输入
input

5
4 5 2 1 4

output

3

explanation
可以划分成 3 个好的子序列： [4], [5,4], [2,1] 。

数据范围
对于 40% 的数据， \(n≤5000\) 。

对于 100% 的数据， \(n≤10^6,1≤A_i≤10^6\) 。

时间限制: 3s
空间限制: 256MB

对于一个数，如果前面的数用不上他，那么就把他作为新的一个子序列的开始。每次找到在\(b_{i-1}-1\)的这种数中第一个既没被用又是最前面的，那么我们就可以选择他。根据贪心，肯定是越前面的可以选择越多数。

#include
#include
using namespace std;
const int N=1e6+5;
int n,a[N],v[N],hd[N],nt[N],cnt,k,f;
setg[N];
set::iterator it;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	for(int i=1;i<=n;i++)
		g[a[i]].insert(i);
	for(int i=1;i<=n;i++)
	{
		if(!v[i])
		{
			k=a[i]-1,f=i,++cnt;
			while(k>0&&!g[k].empty())
			{
				it=g[k].upper_bound(f);
				if(it==g[k].end())
					break;
				f=*it,v[*it]=1,g[k].erase(it),k--;
			}
		}
	}
	printf("%d",cnt);
	return 0;
}