CF911E.Stack Sorting

Let's suppose you have an array a, a stack s (initially empty) and an array b (also initially empty).

You may perform the following operations until both a and s are empty:

• Take the first element of a, push it into s and remove it from a (if a is not empty);
• Take the top element from s, append it to the end of array b and remove it from s (if s is not empty).

You can perform these operations in arbitrary order.

If there exists a way to perform the operations such that array b is sorted in non-descending order in the end, then array a is called stack-sortable.

For example, [3, 1, 2] is stack-sortable, because b will be sorted if we perform the following operations:

1. Remove 3 from a and push it into s;
2. Remove 1 from a and push it into s;
3. Remove 1 from s and append it to the end of b;
4. Remove 2 from a and push it into s;
5. Remove 2 from s and append it to the end of b;
6. Remove 3 from s and append it to the end of b.

After all these operations b = [1, 2, 3], so [3, 1, 2] is stack-sortable. [2, 3, 1] is not stack-sortable.

You are given k first elements of some permutation p of size n (recall that a permutation of size n is an array of size n where each integer from 1 to n occurs exactly once). You have to restore the remaining n - k elements of this permutation so it is stack-sortable. If there are multiple answers, choose the answer such that p is lexicographically maximal (an array q is lexicographically greater than an array p iff there exists some integer k such that for every i < k q__i = p__i, and q__k > p__k). You may not swap or change any of first k elements of the permutation.

Print the lexicographically maximal permutation p you can obtain.

If there exists no answer then output -1.

假设你有一个数组 $a$、一个栈 $s$（初始为空）以及另一个数组 $b$（也初始为空）。

你可以执行以下操作，直到 $a$ 和 $s$ 均为空：

• 取出 $a$ 的首元素，将其压入栈 $s$，并从 $a$ 中删除该元素（当 $a$ 非空时）；
• 取出栈 $s$ 的栈顶元素，将其追加到数组 $b$ 末尾，并从 $s$ 中弹出该元素（当 $s$ 非空时）。

上述操作可以以任意顺序执行。

若存在一种操作序列，使得最终数组 $b$ 按非降序排列，则称数组 $a$ 是栈可排序的（stack-sortable）。

例如，$[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$ 的排列是指由 $1$ 到 $n$ 的每个整数恰好出现一次组成的长度为 $n$ 的数组）。你需要补全该排列剩余的 $n - k$ 个元素，使得整个排列 $p$ 是栈可排序的。若存在多种方案，请选择字典序最大的排列 $p$（数组 $q$ 字典序大于数组 $p$ 当且仅当存在某个整数 $k$，使得对所有 $i < k$ 有 $q_i = p_i$，且 $q_k > p_k$）。你不得交换或修改排列 $p$ 的前 $k$ 个元素。

请输出你能得到的字典序最大的排列 $p$。

若不存在满足条件的排列，则输出 $-1$。

The first line contains two integers n and k (2 ≤ n ≤ 200000, 1 ≤ k < n) — the size of a desired permutation, and the number of elements you are given, respectively.

The second line contains k integers _p_1, _p_2, ..., p__k (1 ≤ p__i ≤ n) — the first k elements of p. These integers are pairwise distinct.

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 200000$，$1 \leq k < n$）——分别为所求排列的长度，以及你被给定的元素个数。

第二行包含 $k$ 个整数 $p_1, p_2, \dots, p_k$（$1 \leq p_i \leq n$）——即排列 $p$ 的前 $k$ 个元素。这些整数两两互不相同。

If it is possible to restore a stack-sortable permutation p of size n such that the first k elements of p are equal to elements given in the input, print lexicographically maximal such permutation.

Otherwise print -1.

如果可以恢复一个大小为 $n$ 的可栈排序排列 $p$，使得 $p$ 的前 $k$ 个元素等于输入中给出的元素，则输出字典序最大的这样的排列。
否则输出 $-1$。