CF911E Stack Sorting

假设你有一个数组 $a$，一个栈 $s$（初始为空），还有一个数组 $b$（初始也为空）。 你可以进行如下操作直到 $a$ 和 $s$ 均为空为止： - 取出 $a$ 的第一个元素，压入 $s$，并从 $a$ 中移除（如果 $a$ 非空）； - 取出 $s$ 栈顶元素，加入到 $b$ 的末尾，并从 $s$ 中移除（如果 $s$ 非空）。 你可以以任意次序执行这些操作。 如果存在一种操作顺序，使得最终数组 $b$ 按非降顺序排列，那么我们称数组 $a$ 是可栈排序的。 例如，$[3,1,2]$ 是可栈排序的，因为如果执行如下操作，$b$ 就会有序： 1. 将 $3$ 从 $a$ 移动到 $s$； 2. 将 $1$ 从 $a$ 移动到 $s$； 3. 将 $1$ 从 $s$ 移动到 $b$； 4. 将 $2$ 从 $a$ 移动到 $s$； 5. 将 $2$ 从 $s$ 移动到 $b$； 6. 将 $3$ 从 $s$ 移动到 $b$。 所有操作完成后，$b=[1,2,3]$，所以 $[3,1,2]$ 是可栈排序的。而 $[2,3,1]$ 不是可栈排序的。 现在给定了某个长度为 $n$ 的排列 $p$ 的前 $k$ 个元素（回忆：长度为 $n$ 的排列是指长度为 $n$ 的数组，其中每个 $1$ 到 $n$ 的整数恰好出现一次）。你需要补全剩下的 $n-k$ 个元素，使得整个排列 $p$ 是可栈排序的。如果有多种方案，选择字典序最大的那个（如果对于某个 $k$，$q$ 和 $p$ 在前 $k-1$ 项都相同，第 $k$ 项有 $q_k > p_k$，则 $q$ 的字典序更大）。你不能更改已给定的前 $k$ 个数。 请输出你能构造出的字典序最大的可栈排序排列 $p$。 如果不存在，输出 $-1$。

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 200000$，$1 \le k < n$）——排列的长度和已给定的前缀长度。 第二行包含 $k$ 个整数 $p_1,p_2,\ldots,p_k$（$1\le p_i\le n$），表示排列 $p$ 的前 $k$ 个元素。这些数字互不相同。

如果存在一种方案能补全排列 $p$ 使其可栈排序，请输出字典序最大的方案。 否则，输出 $-1$。

由 ChatGPT 5 翻译