分数: 400 点
问题陈述
给你一个正整数 N 和一系列 M 正整数 A = (A_{1}, A_{2}, \dots, A_{M}).
这里,所有元素 A 是之间不同的整数 1 和 N,包括在内。
排列 P = (P_{1}, P_{2}, \dots, P_{N}) of (1, 2, \dots, N) 被称为 良好的排列 当所有整数满足以下条件时 i 这样 1 \leq i \leq M:
- 没有连续的子序列 P 是一个排列 (1, 2, \dots, A_{i}).
确定是否 良好的排列 存在,如果存在,则找到字典顺序最小的 良好的排列.
什么是字典顺序?
一个序列 S = (S_1, S_2, \ldots, S_{|S|}) 据说是 按字典顺序较小 比序列 T = (T_1, T_2, \ldots, T_{|T|}) 如果满足以下条件之一。 在这里, |S| 和 |T| 表示的长度 S 和 T。
- |S| \lt |T| 和 (S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|}).
- 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两者成立:
- (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1}).
- S_i 小于 T_i (作为数字)。
约束
- 1 \leq M \leq N \leq 2 \times 10^{5}
- 1 \leq A_{i} \leq N
- 的所有元素 A 是不同的。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
A_{1} A_{2} \cdots A_{M}
输出
如果 良好的排列 不存在,打印 -1.
如果存在,则打印字典顺序最小的 良好的排列,用空格分隔。
示例输入 1
4 1 2
示例输出 1
1 3 2 4
例如, (4, 2, 1, 3) 不是 良好的排列 因为它包含 (2, 1) 作为连续的子序列。
其他非良好的排列 是 (1, 2, 3, 4) 和 (3, 4, 2, 1).
一些 良好的排列 是 (4, 1, 3, 2) 和 (2, 3, 4, 1)。其中,字典顺序最小的是 (1, 3, 2, 4),因此打印时用空格分隔。
示例输入 2
5 3 4 3 2
示例输出 2
1 3 4 5 2
示例 良好的排列 包括 (3, 4, 1, 5, 2), (2, 4, 5, 3, 1),和 (4, 1, 5, 2, 3).
非示例良好的排列 包括 (1, 2, 5, 3, 4), (2, 3, 4, 1, 5),和 (5, 3, 1, 2, 4).
示例输入 3
92 4 16 7 1 67
示例输出 3
-1
如果 良好的排列 不存在,打印 -1.
示例输入 4
43 2 43 2
示例输出 4
-1