原题

题目描述

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

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

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

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

输入格式

第一行包含一个正整数 $n$。

第二行包含 $n$ 个整数，依次表示 $a_1, a_2, \dots, a_n$。

输出格式

输出一行 $n$ 个正整数，相邻两个整数之间用一个空格隔开，第 $i$ 个数字表示用前 $i$ 个套娃最多能套多少层。

样例输入 1

5
1 2 3 4 5

样例输出 1

1 1 2 2 3

样例输入 2

5
2 4 6 8 10

样例输出 2

1 2 3 4 5

样例输入 3

5
3 3 1 3 2

样例输出 3

1 1 2 2 2

说明

其它样例说明

• 样例 $4 \sim 7$：见选手目录下的 doll/doll4.in ~ 7.in 与相应的 .ans，这些样例分别满足子任务 $1 \sim 4$ 的约束条件。

数据范围

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

各子任务的附加限制如下表所示：

点击下载大样例