【题目描述】

我们定义 $f(S)$。设 $S$ 是一个非负整数的多重集（即可以包含重复元素）。每次操作，你可以选择 $S$ 的任意非空子集（也可以包含重复元素），将该子集中的所有元素从 $S$ 中移除，并将该子集的 MEX 加入 $S$。你可以进行任意次这样的操作。所有操作结束后，$S$ 中应只剩下恰好一个数。$f(S)$ 表示通过任意操作序列后，$S$ 最终可能剩下的最大数。

给定一个长度为 $n$ 的非负整数数组 $a$。对于它的每个前缀，计算 $f(S)$，其中 $S$ 是对应的前缀（对于第 $i$ 个前缀，$S$ 包含数组 $a$ 的前 $i$ 个元素）。

MEX 指的是一个数组中未出现的最小非负整数。

【输入格式】

第一行包含一个整数 $n$（$1 \leq n \leq 4 \times 10^5$）——数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 4 \times 10^5$）——数组 $a$。

输出格式

输出 $n$ 个数：对于数组 $a$ 的每个前缀，输出对应 $S$ 的 $f(S)$。

输入输出样例 1

输入输出样例 2

输入输出样例 3

输入输出样例 4~9

分别满足 1~6 子任务的限制。

说明/提示

样例 1 解释

对于长度为 $1$ 的前缀，初始多重集为 $\{179\}$。如果什么都不做，结果就是 $179$。

对于长度为 $2$ 的前缀，初始多重集为 $\{57, 179\}$。可以通过如下操作序列得到 $2$：

1. 对 $\{57\}$ 进行操作，多重集变为 $\{0, 179\}$。
2. 对 $\{179\}$ 进行操作，多重集变为 $\{0, 0\}$。
3. 对 $\{0\}$ 进行操作，多重集变为 $\{0, 1\}$。
4. 对 $\{0, 1\}$ 进行操作，多重集变为 $\{2\}$。这就是答案。

数据规模与约定

对于所有测试数据，保证：

• $1 \leq n \leq 4\times 10^5$；
• $0 \leq a_i\leq 4\times 10^5$；