假设您有一个数组 a、一个堆栈 s(最初为空)和一个数组 b(最初也为空)。
您可以执行以下操作,直到a和s都为空:
- 取出a的第一个元素,将其推入s并将其从a中删除(如果a不为空);
- 从 s 中取出顶部元素,将其附加到数组 b 的末尾并将其从 s 中删除(如果 s 不为空)。
您可以按任意顺序执行这些操作。
如果存在一种方法来执行操作,使得数组 b 最终按非降序排序,则数组 a 称为可堆栈排序。
例如,[3, 1, 2] 是可堆栈排序的,因为如果我们执行以下操作,b 将被排序:
1、将a中的3取出,推入s中;
2、将a中的1取出,推入s中;
3、将s中的1去掉,追加到b的末尾;
4、将a中的2取出,推入s中;
5、将s中的2去掉,追加到b的末尾;
6. 从 s 中删除 3 并将其附加到 b 的末尾。
经过所有这些操作 b = [1, 2, 3],因此 [3, 1, 2] 是可堆栈排序的。 [2, 3, 1] 不可堆栈排序。
给定大小为 n 的某个排列 p 的前 k 个元素(回想一下,大小为 n 的排列是大小为 n 的数组,其中从 1 到 n 的每个整数只出现一次)。您必须恢复此排列的剩余 n - k 元素,以便它可以堆栈排序。如果有多个答案,请选择使 p 按字典顺序最大的答案(数组 q 按字典顺序大于数组 p,当且仅当存在某个整数 k,使得对于每个 i < k qi = pi,且 qk > pk)。您不得交换或更改排列的前 k 个元素中的任何一个。
打印您可以获得的字典顺序最大排列 p。
如果不存在答案则输出-1。
输入
第一行包含两个整数 n 和 k (2 ≤ n ≤ 200000, 1 ≤ k < n) — 分别是所需排列的大小和给定的元素数量。
第二行包含 k 个整数 p1, p2, ..., pk (1 ≤ pi ≤ n) — p 的前 k 个元素。这些整数是两两不同的。
输出
如果可以恢复大小为 n 的堆栈可排序排列 p,使得 p 的前 k 个元素等于输入中给出的元素,则按字典顺序打印最大的此类排列。
否则打印-1。
示例
输入 #1
5 3 3 2 1
输出 #1
3 2 1 5 4
输入 #2
5 3 2 3 1
输出 #2
-1
输入 #3
5 1 3
输出 #3
3 2 1 5 4
输入#4
5 2 3 4
输出#4
-1