P4309 [TJOI2013] 最长上升子序列

题目描述

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

输入格式

第一行一个整数 $N$，表示我们要将 $1$ 到 $N$ 插入序列中。

接下是 $N$ 个数字，第 $k$ 个数字 $X_k$，表示我们将 $k$ 插入到位置 $X_k(0\le X_k\le k-1,1\le k\le N)$

输出格式

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

输入输出样例 #1

输入 #1

3
0 0 2

输出 #1

1
1
2

说明/提示

$100\%$ 的数据 $n\le10^5$。