← 返回题目列表

Codeforces · 1227/B

B. 盒子

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

排列 $$$p$$$ 是整数序列 $$$p=[p_1, p_2, \dots, p_n]$$$,由 $$$n$$$ 之间的 $$$n$$$ 不同(唯一)正整数组成,包括 $$$1$$$ 和 $$$n$$$(含)。例如,以下序列是排列:$$$[3, 4, 1, 2]$$$、$$$[1]$$$、$$$[1, 2]$$$。以下序列不是排列:$$$[0]$$$、$$$[1, 2, 1]$$$、$$$[2, 3]$$$、$$$[0, 1, 2]$$$。

重要的钥匙在您需要打开的上锁的盒子里。要打开盒子,您需要输入密码。密码是长度为$$$n$$$的排列$$$p$$$。

你不知道这个排列,你只知道这个排列的前缀最大值的数组$$$q$$$。正式:

- $$$q_1=p_1$$$,
- $$$q_2=\max(p_1, p_2)$$$,
- $$$q_3=\max(p_1, p_2,p_3)$$$,
- ...
- $$$q_n=\max(p_1, p_2,\dots,p_n)$$$。

您想要构造任何可能的合适排列(即任何此类排列,为此排列计算出的 $$$q$$$ 等于给定的数组)。

输入

第一行包含整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 10^{5})$$$ — 密码排列 $$$p$$$ 中的元素数量。

测试用例的第二行包含 $$$n$$$ 整数 $$$q_1, q_2, \dots, q_n$$$ $$$(1 \le q_i \le n)$$$ — 用于秘密排列的数组 $$$q$$$ 的元素。对于所有$$$i$$$ ($$$1 \le i < n$$$),保证$$$q_i \le q_{i+1}$$$。

输入中所有测试用例的所有值 $$$n$$$ 的总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印:

- 如果不可能找到这样的排列 $$$p$$$,则打印“-1”(不带引号)。
- 否则,打印 $$$n$$$ 不同的整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$)。如果有多个可能的答案,您可以打印其中任何一个。

示例

输入 #1

4
5
1 3 4 5 5
4
1 1 3 4
2
2 2
1
1

输出 #1

1 3 4 5 2 
-1
2 1 
1

注意

在示例答案的第一个测试用例中 $$$[1,3,4,5,2]$$$ 是唯一可能的答案:

- $$$q_{1} = p_{1} = 1$$$;
- $$$q_{2} = \max(p_{1}, p_{2}) = 3$$$;
- $$$q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4$$$;
- $$$q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5$$$;
- $$$q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5$$$。

可以证明示例的第二个测试用例没有答案。