시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB76322356.098%

문제

Marc is teaching some children about objects with different sizes. To demonstrate this concept, he will be using dolls. These dolls are hollow on the inside, so smaller dolls can be placed inside larger ones.

Each doll has a certain size. A doll of size $x$ can fit inside another doll of size $y$ if $y - x ≥ 2$. In other words, a smaller doll can fit in a larger doll if the difference in size between the larger doll and the smaller doll is at least $2$.

A doll stack is formed by selecting some dolls that Marc has and repeatedly fitting the smallest doll into the second smallest doll until only one doll is left. The size of a doll stack is the number of dolls used to create it.

There are n days. On the $i$th ($1 ≤ i ≤ n$) day, Marc will buy a doll of size $a[i]$. After buying the doll, he will try to construct a doll stack with the maximum number of dolls. Help Marc compute, for each day, the maximum size of a doll stack using the dolls available on that day.

입력

The first line of input contains exactly $1$ integer, $n$.

The second line contain $n$ integers $a[1], a[2], \dots , a[n]$, representing the sizes of the dolls bought on each of the $n$ days.

출력

The output should contain $n$ integers on a single line and separated by spaces. The $i$-th integer should be the maximum size of a doll stack using the dolls available on that day.

제한

  • $1 ≤ n ≤ 100\,000$
  • $1 ≤ a[i] ≤ 500\,000$

서브태스크

번호배점제한
123

$n ≤ 200$

214

$a[i]$ is not a multiple of $2$ for all $i$ ($1 ≤ i ≤ n$)

327

$a[i]$ is not a multiple of $4$ for all $i$ ($1 ≤ i ≤ n$)

436

No additional restrictions

예제 입력 1

5
1 2 3 4 5

예제 출력 1

1 1 2 2 3

Day $1$: Marc can only stack doll $1$.

Day $2$: Marc can stack either doll of size $1$ or doll of size $2$.

Day $3$: Marc can stack doll of size $1$ and doll of size $3$. He cannot stack all $3$ dolls as doll of size $2$ does not fit inside doll of size $3$.

Day $4$: Marc can stack either doll of size $1$ and doll of size $3$, doll of size $1$ and doll of size $4$ or doll of size $2$ and doll of size $4$.

Day $5$: Marc can stack doll $1$, $3$ and $5$.

예제 입력 2

5
2 4 6 8 10

예제 출력 2

1 2 3 4 5

All dolls can be stacked as each day passes because the gap between adjacent dolls is equal to $2$.

예제 입력 3

5
3 3 1 3 2

예제 출력 3

1 1 2 2 2

On the first $2$ days, Marc can only stack $1$ doll of size $3$.

On the $3$rd day, Marc can stack the doll of size $1$.

On the $5$th day, Marc cannot stack the doll of size $2$ because the gap between the doll of size $3$ and itself is exactly $1$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.