English · Original
Chinese · Translation
Formal · Original
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_.
## Input
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.
## Output
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_.
[samples]
假设你有一个数组 #cf_span[a]，一个栈 #cf_span[s]（初始为空），以及一个数组 #cf_span[b]（也初始为空）。
你可以执行以下操作，直到 #cf_span[a] 和 #cf_span[s] 都为空：
你可以按任意顺序执行这些操作。
如果存在一种操作方式，使得最终数组 #cf_span[b] 按非降序排列，则称数组 #cf_span[a] 为 _栈排序的_（_stack-sortable_）。
例如，#cf_span[[3, 1, 2]] 是 _栈排序的_，因为如果我们执行以下操作，#cf_span[b] 将会排序：
所有操作结束后，#cf_span[b = [1, 2, 3]]，因此 #cf_span[[3, 1, 2]] 是 _栈排序的_。而 #cf_span[[2, 3, 1]] 不是 _栈排序的_。
现在给你某个大小为 #cf_span[n] 的排列 #cf_span[p] 的前 #cf_span[k] 个元素（回忆一下，大小为 #cf_span[n] 的排列是包含从 #cf_span[1] 到 #cf_span[n] 每个整数恰好一次的数组）。你需要恢复该排列的剩余 #cf_span[n - k] 个元素，使其成为 _栈排序的_。如果有多个答案，请选择使得 #cf_span[p] 字典序最大的那个（数组 #cf_span[q] 字典序大于数组 #cf_span[p] 当且仅当存在某个整数 #cf_span[k]，使得对所有 #cf_span[i < k] 都有 #cf_span[qi = pi]，且 #cf_span[qk > pk]）。*你不能交换或更改排列的前 #cf_span[k] 个元素*。
请输出你能得到的字典序最大的排列 #cf_span[p]。
如果无解，请输出 _-1_。
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 200000]，#cf_span[1 ≤ k < n]）——所需排列的大小，以及你已知的元素个数。
第二行包含 #cf_span[k] 个整数 #cf_span[p1], #cf_span[p2], ..., #cf_span[pk]（#cf_span[1 ≤ pi ≤ n]）——#cf_span[p] 的前 #cf_span[k] 个元素。这些整数互不相同。
如果存在一种方式，恢复一个大小为 #cf_span[n] 的 _栈排序的_ 排列 #cf_span[p]，使得其前 #cf_span[k] 个元素与输入一致，请输出字典序最大的这样的排列。
否则输出 _-1_。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 200000]，#cf_span[1 ≤ k < n]）——所需排列的大小，以及你已知的元素个数。第二行包含 #cf_span[k] 个整数 #cf_span[p1], #cf_span[p2], ..., #cf_span[pk]（#cf_span[1 ≤ pi ≤ n]）——#cf_span[p] 的前 #cf_span[k] 个元素。这些整数互不相同。
## Output
如果存在一种方式，恢复一个大小为 #cf_span[n] 的 _栈排序的_ 排列 #cf_span[p]，使得其前 #cf_span[k] 个元素与输入一致，请输出字典序最大的这样的排列。否则输出 _-1_。
[samples]
**Definitions**
Let $ n, k \in \mathbb{Z}^+ $ with $ 2 \leq n \leq 200000 $, $ 1 \leq k < n $.
Let $ P = (p_1, p_2, \dots, p_n) $ be a permutation of $ \{1, 2, \dots, n\} $.
Let $ A = (p_1, p_2, \dots, p_k) $ be the given prefix of $ P $, with all $ p_i $ distinct and $ 1 \leq p_i \leq n $.
Let $ S $ be a stack (LIFO), initially empty.
Let $ B = (b_1, b_2, \dots, b_n) $ be the output sequence, initially empty.
**Operations**
At each step, one of the following is performed (until both $ A $ and $ S $ are empty):
- Push the next element from $ A $ onto $ S $, or
- Pop the top element from $ S $ and append it to $ B $.
**Constraint**
$ B $ must be sorted in non-descending order: $ b_1 \leq b_2 \leq \dots \leq b_n $.
**Objective**
Extend $ A $ to a full permutation $ P $ of $ \{1, \dots, n\} $ such that $ P $ is *stack-sortable*, and among all such extensions, choose the lexicographically maximal one.
If no such extension exists, output $-1$.
**Given**
The first $ k $ elements $ p_1, \dots, p_k $ are fixed. The remaining $ n - k $ elements must be chosen from $ \{1, \dots, n\} \setminus \{p_1, \dots, p_k\} $, each exactly once.
API Response (JSON)
{
"problem": {
"name": "E. Stack Sorting",
"description": {
"content": "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 fi",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF911E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Let's suppose you have an array _a_, a stack _s_ (initially empty) and an array _b_ (also initially empty).\n\nYou may perform the following operations until both _a_ and _s_ are empty:\n\n* Take the fi...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "假设你有一个数组 #cf_span[a]，一个栈 #cf_span[s]（初始为空），以及一个数组 #cf_span[b]（也初始为空）。\n\n你可以执行以下操作，直到 #cf_span[a] 和 #cf_span[s] 都为空：\n\n你可以按任意顺序执行这些操作。\n\n如果存在一种操作方式，使得最终数组 #cf_span[b] 按非降序排列，则称数组 #cf_span[a] 为 _栈排序的_（_sta...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 2 \\leq n \\leq 200000 $, $ 1 \\leq k < n $. \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $. \nLet $ A = (p_1, p_2,...",
"is_translate": false,
"language": "Formal"
}
]
}