题目描述

给定一个序列，初始为空。现在我们将 $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$ 位置后序列的最长上升子序列的长度是多少。

3
0 0 2

1
1
2

提示

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