{"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 first element of _a_, push it into _s_ and remove it from _a_ (if _a_ is not empty);\n*   Take the top element from _s_, append it to the end of array _b_ and remove it from _s_ (if _s_ is not empty).\n\nYou can perform these operations in arbitrary order.\n\nIf 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_.\n\nFor example, \\[3, 1, 2\\] is _stack-sortable_, because _b_ will be sorted if we perform the following operations:\n\n1.  Remove 3 from _a_ and push it into _s_;\n2.  Remove 1 from _a_ and push it into _s_;\n3.  Remove 1 from _s_ and append it to the end of _b_;\n4.  Remove 2 from _a_ and push it into _s_;\n5.  Remove 2 from _s_ and append it to the end of _b_;\n6.  Remove 3 from _s_ and append it to the end of _b_.\n\nAfter all these operations _b_ = \\[1, 2, 3\\], so \\[3, 1, 2\\] is _stack-sortable_. \\[2, 3, 1\\] is not _stack-sortable_.\n\nYou 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**.\n\nPrint the lexicographically maximal permutation _p_ you can obtain.\n\nIf there exists no answer then output _\\-1_.\n\n## Input\n\nThe 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.\n\nThe 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\n## Output\n\nIf 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.\n\nOtherwise print _\\-1_.\n\n[samples]","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] 为 _栈排序的_（_stack-sortable_）。\n\n例如，#cf_span[[3, 1, 2]] 是 _栈排序的_，因为如果我们执行以下操作，#cf_span[b] 将会排序：\n\n所有操作结束后，#cf_span[b = [1, 2, 3]]，因此 #cf_span[[3, 1, 2]] 是 _栈排序的_。而 #cf_span[[2, 3, 1]] 不是 _栈排序的_。\n\n现在给你某个大小为 #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] 个元素*。\n\n请输出你能得到的字典序最大的排列 #cf_span[p]。\n\n如果无解，请输出 _-1_。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 200000]，#cf_span[1 ≤ k < n]）——所需排列的大小，以及你已知的元素个数。\n\n第二行包含 #cf_span[k] 个整数 #cf_span[p1], #cf_span[p2], ..., #cf_span[pk]（#cf_span[1 ≤ pi ≤ n]）——#cf_span[p] 的前 #cf_span[k] 个元素。这些整数互不相同。\n\n如果存在一种方式，恢复一个大小为 #cf_span[n] 的 _栈排序的_ 排列 #cf_span[p]，使得其前 #cf_span[k] 个元素与输入一致，请输出字典序最大的这样的排列。\n\n否则输出 _-1_。\n\n## Input\n\n第一行包含两个整数 #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] 个元素。这些整数互不相同。\n\n## Output\n\n如果存在一种方式，恢复一个大小为 #cf_span[n] 的 _栈排序的_ 排列 #cf_span[p]，使得其前 #cf_span[k] 个元素与输入一致，请输出字典序最大的这样的排列。否则输出 _-1_。\n\n[samples]","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, \\dots, p_k) $ be the given prefix of $ P $, with all $ p_i $ distinct and $ 1 \\leq p_i \\leq n $.  \nLet $ S $ be a stack (LIFO), initially empty.  \nLet $ B = (b_1, b_2, \\dots, b_n) $ be the output sequence, initially empty.  \n\n**Operations**  \nAt each step, one of the following is performed (until both $ A $ and $ S $ are empty):  \n- Push the next element from $ A $ onto $ S $, or  \n- Pop the top element from $ S $ and append it to $ B $.  \n\n**Constraint**  \n$ B $ must be sorted in non-descending order: $ b_1 \\leq b_2 \\leq \\dots \\leq b_n $.  \n\n**Objective**  \nExtend $ 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.  \nIf no such extension exists, output $-1$.  \n\n**Given**  \nThe 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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF911E","tags":["constructive algorithms","data structures","greedy","implementation"],"sample_group":[["5 3\n3 2 1","3 2 1 5 4"],["5 3\n2 3 1","\\-1"],["5 1\n3","3 2 1 5 4"],["5 2\n3 4","\\-1"]],"created_at":"2026-03-03 11:00:39"}}