← 返回题目列表

Codeforces · 911/E

E. 堆栈排序

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

假设您有一个数组 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