Problem Description

Marc is teaching kindergarten children, and he chooses nesting dolls to help them understand the sizes of objects.

Each nesting doll has its own size, denoted by $a$. If the sizes $a_x$ and $a_y$ of two dolls $x$ and $y$ satisfy $a_x-a_y\ge2$, then doll $y$ can be put inside doll $x$.

Clearly, dolls can be nested in multiple layers. So Marc wants you to answer some questions:

These questions last for $n$ days. On day $i$, Marc buys a nesting doll of size $a_i$. After buying the $i$-th doll, he wants you to find the maximum number of layers that can be nested using the first $i$ dolls.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers, representing $a$.

Output Format

Output one line with $n$ positive integers. The $i$-th integer represents the maximum number of layers that can be nested using the first $i$ dolls.

5
1 2 3 4 5

1 1 2 2 3

5
2 4 6 8 10

1 2 3 4 5

5
3 3 1 3 2

1 1 2 2 2

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 100000,1 \le a_i \le 500000$.

Translated by ChatGPT 5