Problem Description

Marc is teaching kindergarten kids using nesting dolls to help them understand the concept of size.

A nesting doll has its own size, denoted as $a$. If the sizes $a_x$ and $a_y$ of two nesting dolls $x$ and $y$ satisfy $a_x - a_y \ge 2$, then doll $y$ can be placed inside doll $x$.

Clearly, nesting dolls can be nested multiple layers deep. Therefore, Marc wants you to answer some questions:

These questions span $n$ days. On the $i$-th day, Marc buys a nesting doll of size $a_i$. He wants you to determine, after buying the $i$-th doll, the maximum number of layers that can be nested using the first $i$ dolls.

Input Format

The first line contains a single positive integer $n$.

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

Output Format

A single line containing $n$ positive integers, where the $i$-th integer represents the maximum number of layers that can be nested using the first $i$ dolls.

Sample Input and Output

Sample Input #1

5
1 2 3 4 5

Sample Output #1

1 1 2 2 3

Sample Input #2

5
2 4 6 8 10

Sample Output #2

1 2 3 4 5

Sample Input #3

5
3 3 1 3 2

Sample Output #3

1 1 2 2 2

Notes

Data Range

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

见题面 Input 部分

见题面 Output 部分