P4309 [TJOI2013] Longest Increasing Subsequence

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.

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 $N$ lines. The $i$-th line is the length of the longest increasing subsequence after inserting $i$ at position $X_i$.

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