给定一个正整数序列,如果某个正整数出现的次数是任何正整数出现的最大次数,则该正整数称为该序列的众数。例如$$$[2,2,3]$$$的模式是$$$2$$$。 $$$9$$$、$$$8$$$ 或 $$$7$$$ 中的任何一个都可以被视为序列 $$$[9,9,8,8,7,7]$$$ 的众数。
你给了 UFO 一个长度为 $$$n$$$ 的数组 $$$a$$$。为了感谢您,UFO 决定构造另一个长度为 $$$n$$$ 的数组 $$$b$$$,使得 $$$a_i$$$ 是所有 $$$1 \leq i \leq n$$$ 的序列 $$$[b_1, b_2, \ldots, b_i]$$$ 的众数。
然而,UFO 不知道如何构造数组$$$b$$$,所以你必须帮助她。请注意,$$$1 \leq b_i \leq n$$$ 必须适用于所有 $$$1 \leq 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$$$总是可以构造的。如果有多个可能的数组,您可以打印任何一个。
示例
输入 #1
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
1 2 1 1 2 2 4 5 5 1 1 2 2 3 1 8 2 2 1 3 3 9 1 1
注意
让我们验证测试用例 $$$2$$$ 中示例输出的正确性。
- 当 $$$i = 1$$$ 时,$$$1$$$ 是 $$$[1]$$$ 唯一可能的模式。
- 当 $$$i = 2$$$ 时,$$$1$$$ 是 $$$[1, 1]$$$ 的唯一可能模式。
- 当 $$$i = 3$$$ 时,$$$1$$$ 是 $$$[1, 1, 2]$$$ 的唯一可能模式。
- 当 $$$i = 4$$$ 时,$$$1$$$ 或 $$$2$$$ 都是 $$$[1, 1, 2, 2]$$$ 的模式。由于 $$$a_i = 2$$$,该数组有效。