最长上升子序列

最长上升子序列

题目描述

给定一个序列,初始为空。现在我们将1到N的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?

输入格式

第一行一个整数N,表示我们要将1到N插入序列中,接下是N个数字,第k个数字Xk,表示我们将k插入到位置Xk(0<=Xk<=k-1,1<=k<=N)

输出格式

N行,第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。

样例输入

3
0 0 2

样例输出

1
1
2

提示

100%的数据 n<=100000

信息

难度
8
分类
(无)
标签
递交数
23
已通过
4
通过率
17%
上传者