题目描述

定义一个可重集合是不相邻集合当且仅当集合中任意两个数的差 $\ge 2$。比如 $\{1,3,6,8\}$ 是一个不相邻集合，而 $\{1,2,3\}$ 和 $\{2,2,6\}$ 不是。

菜汪酱有一个序列 $a_1,a_2,\dots a_n$。对于每个前缀 $a_1,\dots ,a_i$，请你求出从这些元素中选择一些能组成的最大的不相邻集合的大小。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots a_n$。

输出格式

输出一行 $n$ 个用空格分隔的整数，表示从每个前缀能选出的最大不相邻集合的大小。

输入输出样例

样例输入#1

5
1 2 3 4 5

样例输出#1

1 1 2 2 3

样例输入#2

5
3 3 1 3 2

样例输出#2

1 1 2 2 2

样例输入/输出#3/#4

见下发文件。

数据范围

对于 $20\%$ 的数据，$n\le 200$。

对于 $40\%$ 的数据，$n\le 1000$。

对于另外 $10\%$ 的数据，保证所有 $a_i$ 都是奇数。

对于另外 $20\%$ 的数据，保证所有 $a_i$ 都不是 $4$ 的倍数。

对于 $100\%$ 的数据，$1\le n\le 3\times 10^5$，$1\le a_i\le 5\times 10^5$。