310690: CF1870G. MEXanization

G. MEXanizationtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

4
8
179 57 2 0 2 3 2 3
1
0
3
1 0 3
8
1 0 1 2 4 3 0 2

Output

179 2 3 3 3 4 4 5 
1 
1 2 2 
1 2 2 3 3 5 5 5 

Note

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.

题目大意：
定义一个函数 f(S)，其中 S 是一个包含非负整数的多重集合（即可以包含重复元素）。你可以进行以下操作：选择 S 的任意非空子集（也可以包含重复元素），从 S 中移除这个子集（包括其中的所有元素），并将移除子集的 MEX 值添加到 S 中。你可以执行任意次数的这种操作。经过所有操作后，S 中应该只包含一个数字。f(S) 是在执行任意序列的操作后 S 中可能剩余的最大数字。

给你一个长度为 n 的非负整数数组 a。对于它的 n 个前缀，计算当 S 是对应前缀时的 f(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 不属于。

输入输出数据格式：
输入：
- 第一行包含一个整数 t (1 ≤ t ≤ 10^4) —— 测试用例的数量。然后是测试用例的描述。
- 每个测试用例的第一行包含一个整数 n (1 ≤ n ≤ 2 × 10^5) —— 数组 a 的大小。
- 每个测试用例的第二行包含 n 个整数 a_1, a_2, ..., a_n (0 ≤ a_i ≤ 2 × 10^5) —— 数组 a。
- 保证所有测试用例中所有 n 值的总和不超过 2 × 10^5。

输出：
- 对于每个测试用例，输出 n 个数字：数组 a 的每个前缀的 f(S)。

示例：
输入：
```
4
8
179 57 2 0 2 3 2 3
1
0
3
1 0 3
8
1 0 1 2 4 3 0 2
```
输出：
```
179 2 3 3 3 4 4 5
1
1 2 2
1 2 2 3 3 5 5 5
```题目大意： 定义一个函数 f(S)，其中 S 是一个包含非负整数的多重集合（即可以包含重复元素）。你可以进行以下操作：选择 S 的任意非空子集（也可以包含重复元素），从 S 中移除这个子集（包括其中的所有元素），并将移除子集的 MEX 值添加到 S 中。你可以执行任意次数的这种操作。经过所有操作后，S 中应该只包含一个数字。f(S) 是在执行任意序列的操作后 S 中可能剩余的最大数字。 给你一个长度为 n 的非负整数数组 a。对于它的 n 个前缀，计算当 S 是对应前缀时的 f(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 不属于。 输入输出数据格式： 输入： - 第一行包含一个整数 t (1 ≤ t ≤ 10^4) —— 测试用例的数量。然后是测试用例的描述。 - 每个测试用例的第一行包含一个整数 n (1 ≤ n ≤ 2 × 10^5) —— 数组 a 的大小。 - 每个测试用例的第二行包含 n 个整数 a_1, a_2, ..., a_n (0 ≤ a_i ≤ 2 × 10^5) —— 数组 a。 - 保证所有测试用例中所有 n 值的总和不超过 2 × 10^5。 输出： - 对于每个测试用例，输出 n 个数字：数组 a 的每个前缀的 f(S)。 示例： 输入： ``` 4 8 179 57 2 0 2 3 2 3 1 0 3 1 0 3 8 1 0 1 2 4 3 0 2 ``` 输出： ``` 179 2 3 3 3 4 4 5 1 1 2 2 1 2 2 3 3 5 5 5 ```