← 返回题目列表

Codeforces · 2044/D

D. 更难的问题

中文机器翻译题面 查看原题

给定一个正整数序列,如果某个正整数出现的次数是任何正整数出现的最大次数,则该正整数称为该序列的众数。例如$$$[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$$$,该数组有效。