题目描述

给定一个正整数序列，如果一个正整数出现的次数是任何一个正整数出现的最大次数，那么这个正整数就称为序列的模。例如

• $[2,2,3]$ 的模是 $2$ 。
• $9$ 、 $8$ 或 $7$ 中的任何一个都可视为序列 $[9,9,8,8,7,7]$ 的一个模。

你给了 翁老师 一个长度为 $n$ 的数组 $a$ 。为了感谢你，翁老师 决定再构造一个长度为 $n$ 的数组 $b$ ，使得 $a_i$ 是数列 $[b_1, b_2, \ldots, b_i]$ 中所有 $1 \leq i \leq n$ 的模。

但是，翁老师 不知道如何构造数组 $b$ ，所以你必须帮助他。请注意，在所有 $1 \leq i \leq n$ 中，你的数组 $1 \leq b_i \leq n$ 必须成立。

输入格式

第一行包含 $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$ （ $1 \leq a_i \leq n$ ）。

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

输出格式

对于每个测试用例，在新行中输出 $n$ 数字 $b_1, b_2, \ldots, b_n$ ( $1 \leq b_i \leq 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

数据规模与约定

样例 1 解释

让我们在测试用例 $2$ 中验证样本输出的正确性。

• 当 $i = 1$， $[1]$ 的唯一可能模式。
• 当 $i = 2$， $[1, 1]$ 的唯一可能模式。
• 当 $i = 3$， $1$ 是 $[1, 1, 2]$ 的唯一可能模式。
• 当 $i = 4$， $1$ 或 $2$ 都是 $[1, 1, 2, 2]$ 的模式。