D. Harder Problem
时间限制：每测试 $2$ 秒
内存限制：每测试 $256$ MB

给定一个正整数序列，若某个正整数在该序列中出现的次数最多，则称其为该序列的众数。例如，$[2,2,3]$ 的众数是 $2$。对于 $[9,9,8,8,7,7]$，$9$、$8$、$7$ 中的任意一个都可被视为众数。

你给了 UFO 一个长度为 $n$ 的数组 $a$。为了感谢你，UFO 决定构造另一个长度为 $n$ 的数组 $b$，使得对于所有 $1 \le i \le n$，$a_i$ 是序列 $[b_1, b_2, \dots, b_i]$ 的一个众数。

然而 UFO 不知道如何构造数组 $b$，所以你必须帮助她。注意，对于所有 $1 \le i \le n$，必须满足 $1 \le b_i \le n$。

输入格式
第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试数据组数。
每组测试数据的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$) —— 数组 $a$ 的长度。
接下来的一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。
保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式
对于每组测试数据，在新的一行输出 $n$ 个数字 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$)。可以证明数组 $b$ 总是可以被构造出来。如果存在多个可能的数组，输出任意一个即可。

样例
输入

4
2
1 2
4
1 1 1 2
8
4 5 5 5 1 1 2 1
10
1 1 2 2 1 1 3 3 1 1

输出

1 2
1 1 2 2
4 5 5 1 1 2 2 3
1 8 2 2 1 3 3 9 1 1

说明
以样例中第二组测试数据的输出为例验证正确性：

• $i=1$ 时，$[1]$ 的众数只能是 $1$。
• $i=2$ 时，$[1,1]$ 的众数只能是 $1$。
• $i=3$ 时，$[1,1,2]$ 的众数只能是 $1$。
• $i=4$ 时，$[1,1,2,2]$ 的众数可以是 $1$ 或 $2$。由于 $a_4=2$，该数组是合法的。