Marc 正在向孩子们介绍不同大小的物体。为了演示这个概念，他将使用套娃。这些套娃内部是空心的，因此较小的套娃可以放入较大的套娃中。

每个套娃都有一个特定的大小。如果 $y - x \geq 2$，那么大小为 $x$ 的套娃就可以放入大小为 $y$ 的套娃中。换句话说，如果较大套娃与较小套娃的大小之差至少为 $2$，则较小的套娃可以放入较大的套娃中。

套娃堆是通过选择 Marc 拥有的部分套娃，并重复将最小的套娃放入第二小的套娃中，直到只剩下一个套娃为止而形成的。套娃堆的大小是创建它所使用的套娃数量。

共有 $n$ 天。在第 $i$ 天（$1 \leq i \leq n$），Marc 将购买一个大小为 $a[i]$ 的套娃。购买该套娃后，他将尝试构建一个包含最多套娃的套娃堆。请帮助 Marc 计算每天使用当天可用的套娃所能构建的套娃堆的最大大小。

输入格式

程序必须从标准输入读取数据。

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

第二行包含 $n$ 个整数 $a[1], a[2], \dots, a[n]$，分别代表在 $n$ 天中每一天购买的套娃的大小。

输出格式

程序必须输出到标准输出。

输出应包含一行 $n$ 个整数，并用空格分隔。第 $i$ 个整数应为使用当天可用的套娃所能构建的套娃堆的最大大小。

数据范围

对于所有测试用例，输入满足以下限制：

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

程序将在满足以下限制的输入实例上进行测试：

样例

样例输入 1

5
1 2 3 4 5

样例输出 1

1 1 2 2 3

说明 1

第 1 天：Marc 只能堆叠大小为 1 的套娃。

第 2 天：Marc 可以堆叠大小为 1 或大小为 2 的套娃。

第 3 天：Marc 可以堆叠大小为 1 和大小为 3 的套娃。他不能堆叠所有 3 个套娃，因为大小为 2 的套娃无法放入大小为 3 的套娃中。

第 4 天：Marc 可以堆叠大小为 1 和大小为 3 的套娃，大小为 1 和大小为 4 的套娃，或者大小为 2 和大小为 4 的套娃。

第 5 天：Marc 可以堆叠大小为 1、3 和 5 的套娃。

样例输入 2

5
2 4 6 8 10

样例输出 2

1 2 3 4 5

说明 2

随着每一天的过去，所有套娃都可以被堆叠，因为相邻套娃之间的间隙等于 2。

样例输入 3

5
3 3 1 3 2

样例输出 3

1 1 2 2 2

说明 3

在前 2 天，Marc 只能堆叠 1 个大小为 3 的套娃。

在第 3 天，Marc 可以堆叠大小为 1 的套娃。

在第 5 天，Marc 不能堆叠大小为 2 的套娃，因为大小为 3 的套娃与它之间的间隙恰好为 1。