Prefix MEX Problem
本题没有可用的提交语言。
Description
You are given a sequence of $n$ non-negative integers $a = [a_1, a_2, \dots, a_n]$.
You can perform the following operation any number of times:
- choose an index $i$ ($1 \le i \le n$) and replace $a_i$ by the MEX of the prefix $[a_1, a_2, \dots, a_{i-1}]$. (Note, that in case of choosing $i = 1$, the MEX of an empty prefix is equal to $0$).
Find the lexicographically smallest sequence that can be obtained by performing such operations.
Recall that MEX of a sequence is a minimum non-negative integer that does not belong to the sequence.
A sequence $a$ is lexicographically smaller than a sequence $b$ if and only if one of the following holds:
- $a$ is a prefix of $b$, but $a \ne b$;
- in the first position where $a$ and $b$ differ, the sequence $a$ has a smaller element than the corresponding element in $b$.
The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$).
The second line contains $n$ integers $a_1, a_2, a_3, \dots, a_n$ ($0 \le a_i \le 10^9$).
The sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.
For each test case, output $n$ integers — the lexicographically smallest sequence that can be obtained by performing such operations.
Input
The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$).
The second line contains $n$ integers $a_1, a_2, a_3, \dots, a_n$ ($0 \le a_i \le 10^9$).
The sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.
Output
For each test case, output $n$ integers — the lexicographically smallest sequence that can be obtained by performing such operations.
4
7
0 3 0 1 2 4 0
4
0 1 2 3
5
1 0 1 0 1
3
1 3 5
0 1 0 1 2 3 0
0 1 2 3
0 0 1 0 1
0 0 0
Note
In the first test case, you can perform such $2$ operations:
- choose $i = 2$, then replace $a_2 = 3$ by the MEX of the prefix $[0]$ — $1$.
- choose $i = 6$, then replace $a_6 = 4$ by the MEX of the prefix $[0, 1, 0, 1, 2]$ — $3$.
In the second test case, you can perform no operations.
In the third test case, you can perform a single operation:
- choose $i = 1$, then replace $a_1 = 1$ by the MEX of an empty prefix — $0$.