C. Prefix MEX Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Example
Input
4
7
0 3 0 1 2 4 0
4
0 1 2 3
5
1 0 1 0 1
3
1 3 5
Output
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:

  1. choose $$$i = 2$$$, then replace $$$a_2 = 3$$$ by the MEX of the prefix $$$[0]$$$ — $$$1$$$.
  2. 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:

  1. choose $$$i = 1$$$, then replace $$$a_1 = 1$$$ by the MEX of an empty prefix — $$$0$$$.