P10729 [NOISG 2023 Qualification] Dolls

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.

The first line contains a positive integer $n$. The second line contains $n$ integers, representing $a$.

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.

### Constraints |$\text{Subtask}$|Score|Special Property| |:-:|:-:|:-:| |$0$|$0$|Sample| |$1$|$23$|$n\le200$| |$2$|$14$|$a_i$ is odd| |$3$|$27$|$a_i$ is not a multiple of $4$| |$4$|$36$|None| For $100\%$ of the testdata, $1 \le n \le 100000,1 \le a_i \le 500000$. Translated by ChatGPT 5