CF2044D Harder Problem

给定一个正整数序列，若一个正整数在该序列中出现最多次，则称其为该序列的众数（ mode ）。例如，序列 $[2,2,3]$ 的众数为 $2$ 。 $9$ ， $8$ 或 $7$ 的任意一个都可以被认为是序列 $[9,9,8,8,7,7]$ 的众数。 你给了 UFO 一个长度为 $n$ 的数组 $a$ 。为了感谢你， UFO 决定构造一个长度也为 $n$ 的数组 $b$ ，使得对于所有 $1 \leq i \leq n$ ，$a_i$ 是序列 $[b_1, b_2, …, b_i]$ 的众数。 然而， UFO 不知道怎么构造数组 b ，因此你需要帮助她。注意：构造的数组 b 中的元素 $b_i$ 需满足 $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$ 总是可以构造出来。如果有多个解，输出任意一个。

对第 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$ ，因此这个数组是有效的。