You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

xz 正在教幼儿园的小朋友，他选择套娃来教小朋友们认识物体的大小。

一个套娃有一个自己的尺寸，记为 $a$。如果两个套娃 $x$ 和 $y$ 的尺寸 $a_x$ 和 $a_y$ 可以满足 $a_x-a_y\ge2$，那么套娃 $y$ 可以放在套娃 $x$ 中。

很显然，套娃之间是可以互相嵌套多层的。于是 xz 想请你回答一些问题：

这些问题持续 $n$ 天。在第 $i$ 天，xz购买了一个大小为 $a_i$ 的套娃。他想请你求出，在买完第 $i$ 个套娃后，他用前 $i$ 个套娃最多可以套多少层。

输入格式

第一行，一个正整数 $n$。

第二行 $n$ 个整数，表示 $a$。

输出格式

一行 $n$ 个正整数，第 $i$ 个表示用前 $i$ 个套娃最多能套多少层。

样例 #1

样例输入 #1

5
1 2 3 4 5

样例输出 #1

1 1 2 2 3

样例 #2

样例输入 #2

5
2 4 6 8 10

样例输出 #2

1 2 3 4 5

样例 #3

样例输入 #3

5
3 3 1 3 2

样例输出 #3

1 1 2 2 2

提示

【数据范围】

对于 $100\%$ 的数据，$1 \le n \le 100000,1 \le a_i \le 500000$。