CF1759G Restore the Permutation

一个长度为 $n$ 的数列被称为排列，如果它恰好包含 $1$ 到 $n$ 的所有数字各一次。例如，序列 $[3, 1, 4, 2]$、$[1]$ 和 $[2, 1]$ 是排列，但 $[1, 2, 1]$、$[0, 1]$ 和 $[1, 3, 4]$ 不是排列。 对于一个长度为偶数 $n$ 的排列 $p$，你可以构造一个长度为 $\frac{n}{2}$ 的数组 $b$，使得： - 对于 $1 \le i \le \frac{n}{2}$，有 $b_i = \max(p_{2i - 1}, p_{2i})$ 例如，如果 $p = [2, 4, 3, 1, 5, 6]$，那么： - $b_1 = \max(p_1, p_2) = \max(2, 4) = 4$ - $b_2 = \max(p_3, p_4) = \max(3, 1) = 3$ - $b_3 = \max(p_5, p_6) = \max(5, 6) = 6$ 因此，得到 $b = [4, 3, 6]$。给定数组 $b$，请你找出字典序最小的排列 $p$，使得可以由 $p$ 构造出给定的数组 $b$。 如果 $b = [4, 3, 6]$，那么可以构造出的字典序最小的排列为 $p = [1, 4, 2, 3, 5, 6]$，因为： - $b_1 = \max(p_1, p_2) = \max(1, 4) = 4$ - $b_2 = \max(p_3, p_4) = \max(2, 3) = 3$ - $b_3 = \max(p_5, p_6) = \max(5, 6) = 6$ 一个排列 $x_1, x_2, \dots, x_n$ 的字典序小于排列 $y_1, y_2, \dots, y_n$，当且仅当存在某个 $i$（$1 \le i \le n$），使得 $x_1 = y_1, x_2 = y_2, \dots, x_{i-1} = y_{i-1}$ 且 $x_i < y_i$。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个偶数 $n$（$2 \le n \le 2 \cdot 10^5$）。 每个测试用例的第二行包含恰好 $\frac{n}{2}$ 个整数 $b_i$（$1 \le b_i \le n$），表示数组 $b$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行： - 输出一个字典序最小的排列 $p$，使得可以由它构造出数组 $b$； - 如果不存在这样的排列，输出 $-1$。

第一个测试用例的解析见题目描述。 由 ChatGPT 4.1 翻译