Online Longest Increasing Subsequence Queries

You are given an initially empty sequence. You will perform n insertions. For the i-th insertion, you will insert the number i (i.e. from 1 to n in increasing order) into a specified position in the current sequence. The positions are 1-indexed. After each insertion, output the length of the longest increasing subsequence (LIS) of the current sequence.

The longest increasing subsequence (LIS) of a sequence a₁, a₂, ..., a_k is defined as the longest sequence that can be obtained by deleting some or no elements without changing the order of the remaining elements such that the remaining elements are strictly increasing. In mathematical notation, if b₁, b₂, ..., b_m is an increasing subsequence of a, then it satisfies: \[ b_1 < b_2 < \cdots < b_m \] and m is maximized.

Input Format: The first line contains an integer n, the number of insertions. Each of the following n lines contains an integer p (1 ≤ p ≤ current length of sequence + 1), which indicates the position (1-indexed) at which the current number (which is the next integer from 1 to n) should be inserted into the sequence.

Output Format: After each insertion, output the length of the longest increasing subsequence on a new line.

inputFormat

The input begins with an integer n. The next n lines each contain one integer p (1-indexed) representing the position to insert the current number.

Sample Input:
5
1
1
3
2
5

outputFormat

Output n lines, where the i-th line contains the length of the longest increasing subsequence after the i-th insertion.

Sample Output:
1
1
2
2
3

sample

3
1
1
2

1
1
2