小红出牌（hard）

题号：NC310816
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ （本题为hard难度，两题的差别仅在于本题不保证小红抽到的每张牌都不相同）
$\hspace{15pt}$ 小红定义 $k$ 张牌是一个「顺子」，当且仅当这些牌从小到大排序后，满足对于 $1 \sim k - 1$ 的每个 $i$ ，都有 $a_i+1=a_{i+1}$ 。例如， $\{4,3,6,7,5\}$ 能构成一幅顺子。特殊的，单独的一张牌也是顺子。
$\hspace{15pt}$ 现在小红抽到了 $n$ 张牌。她想知道，对于前 $x$ 张牌而言，小红每次都出顺子的前提下，最少出牌多少次可以出完所有的牌？你需要依次回答 $x \in \left[1,n\right]$ 的每个答案。

输入描述:

第一行输入一个正整数 。
第二行输入  个正整数 ，代表每张牌上面的数字。

输出描述:

输出  个正整数 ，代表对于前  张牌，小红出完所有牌所需的最小次数。

示例1

输入

复制

6
1 3 1 2 3 2

输出

复制

1 2 3 2 3 2

说明

当  为  时：一次打出 。
当  为  时：两次打出  和  。
当  为  时：三次打出 ， 和 。
当  为  时：两次打出  和 。
当  为  时：三次打出  ，  和 。
当  为  时：两次打出  和 。