Description

You are given a sequence that is initially empty. We will insert the numbers $1$ through $N$ into the sequence, each time inserting one number at a specific position. After each insertion, we want to know the length of the current longest increasing subsequence.

Input Format

The first line contains an integer $N$, indicating that we will insert $1$ through $N$ into the sequence.

Then follow $N$ integers. The $k$-th number $X_k$ indicates that we insert $k$ at position $X_k$ ($0 \le X_k \le k - 1$, $1 \le k \le N$).

Output Format

Output $N$ lines. The $i$-th line is the length of the longest increasing subsequence after inserting $i$ at position $X_i$.

3
0 0 2

1
1
2

Hint

Constraints: For $100\%$ of the testdata, $N \le 10^5$.

Translated by ChatGPT 5