CF1870G.MEXanization

Let's define $f(S)$. Let $S$ be a multiset (i.e., it can contain repeated elements) of non-negative integers. In one operation, you can choose any non-empty subset of $S$ (which can also contain repeated elements), remove this subset (all elements in it) from $S$, and add the MEX of the removed subset to $S$. You can perform any number of such operations. After all the operations, $S$ should contain exactly $1$ number. $f(S)$ is the largest number that could remain in $S$ after any sequence of operations.

You are given an array of non-negative integers $a$ of length $n$. For each of its $n$ prefixes, calculate $f(S)$ if $S$ is the corresponding prefix (for the $i$-th prefix, $S$ consists of the first $i$ elements of array $a$).

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
• The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• The MEX of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.

我们定义函数 $f(S)$。设 $S$ 是一个非负整数的多重集（即，其中可以包含重复元素）。一次操作定义为：任选 $S$ 的一个非空子集（该子集也可以包含重复元素），将该子集中的所有元素从 $S$ 中移除，并将该子集的 MEX 值加入 $S$。你可以执行任意多次此类操作。所有操作结束后，$S$ 中必须恰好剩下 $1$ 个数。$f(S)$ 表示在所有可能的操作序列下，最终 $S$ 中所能剩下的最大数值。

给定一个长度为 $n$ 的非负整数数组 $a$。对它的每个长度为 $i$ 的前缀（$i = 1, 2, \dots, n$），计算 $f(S)$ 的值，其中 $S$ 即为该前缀（即第 $i$ 个前缀对应 $S$ 由数组 $a$ 的前 $i$ 个元素构成）。

数组的 MEX（最小未出现值）是指不属于该数组的最小非负整数。例如：

• $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 不在数组中。
• $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 在数组中，但 $2$ 不在。
• $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 都在数组中，但 $4$ 不在。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the size of array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 2 \cdot 10^5$) — the array $a$.

It is guaranteed that the sum of all $n$ values across all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 数组 $a$ 的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 2 \cdot 10^5$）—— 数组 $a$。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output $n$ numbers: $f(S)$ for each of the $n$ prefixes of array $a$.

对于每个测试用例，输出 $n$ 个数：数组 $a$ 的每个长度为 $1,2,\dots,n$ 的前缀 $S$ 对应的 $f(S)$ 值。

Consider the first test case. For a prefix of length $1$, the initial multiset is ${179}$. If we do nothing, we get $179$.

For a prefix of length $2$, the initial multiset is ${57, 179}$. Using the following sequence of operations, we can obtain $2$.

1. Apply the operation to ${57}$, the multiset becomes ${0, 179}$.
2. Apply the operation to ${179}$, the multiset becomes ${0, 0}$.
3. Apply the operation to ${0}$, the multiset becomes ${0, 1}$.
4. Apply the operation to ${0, 1}$, the multiset becomes ${2}$. This is our answer.

Consider the second test case. For a prefix of length $1$, the initial multiset is ${0}$. If we apply the operation to ${0}$, the multiset becomes ${1}$. This is the answer.

考虑第一个测试用例。对于长度为 $1$ 的前缀，初始多重集为 ${179}$。若不进行任何操作，结果为 $179$。

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

1. 对 ${57}$ 应用操作，多重集变为 ${0, 179}$。
2. 对 ${179}$ 应用操作，多重集变为 ${0, 0}$。
3. 对 ${0}$ 应用操作，多重集变为 ${0, 1}$。
4. 对 ${0, 1}$ 应用操作，多重集变为 ${2}$。此即所求答案。

考虑第二个测试用例。对于长度为 $1$ 的前缀，初始多重集为 ${0}$。若对 ${0}$ 应用操作，多重集变为 ${1}$。此即所求答案。