{"raw_statement":[{"iden":"problem statement","content":"You are given a positive integer $N$ and a sequence of $M$ positive integers $A = (A_{1}, A_{2}, \\dots, A_{M})$.\nHere, all elements of $A$ are distinct integers between $1$ and $N$, inclusive.\nA permutation $P = (P_{1}, P_{2}, \\dots, P_{N})$ of $(1, 2, \\dots, N)$ is called a **good permutation** when it satisfies the following condition for all integers $i$ such that $1 \\leq i \\leq M$:\n\n*   No contiguous subsequence of $P$ is a permutation of $(1, 2, \\dots, A_{i})$.\n\nDetermine whether a **good permutation** exists, and if it does, find the lexicographically smallest **good permutation**.\nWhat is lexicographical order?A sequence $S = (S_1, S_2, \\ldots, S_{|S|})$ is said to be **lexicographically smaller** than a sequence $T = (T_1, T_2, \\ldots, T_{|T|})$ if one of the following conditions holds. Here, $|S|$ and $|T|$ denote the lengths of $S$ and $T$, respectively.\n\n1.  $|S| \\lt |T|$ and $(S_1, S_2, \\ldots, S_{|S|}) = (T_1, T_2, \\ldots, T_{|S|})$.\n2.  There exists an integer $1 \\leq i \\leq \\min\\lbrace |S|, |T| \\rbrace$ such that both of the following hold:\n    *   $(S_1, S_2, \\ldots, S_{i-1}) = (T_1, T_2, \\ldots, T_{i-1})$.\n    *   $S_i$ is smaller than $T_i$ (as a number)."},{"iden":"constraints","content":"*   $1 \\leq M \\leq N \\leq 2 \\times 10^{5}$\n*   $1 \\leq A_{i} \\leq N$\n*   All elements of $A$ are distinct.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_{1}$ $A_{2}$ $\\cdots$ $A_{M}$"},{"iden":"sample input 1","content":"4 1\n2"},{"iden":"sample output 1","content":"1 3 2 4\n\nFor example, $(4, 2, 1, 3)$ is not a **good permutation** because it contains $(2, 1)$ as a contiguous subsequence.\nOther non-**good permutations** are $(1, 2, 3, 4)$ and $(3, 4, 2, 1)$.\nSome **good permutations** are $(4, 1, 3, 2)$ and $(2, 3, 4, 1)$. Among these, the lexicographically smallest one is $(1, 3, 2, 4)$, so print it separated by spaces."},{"iden":"sample input 2","content":"5 3\n4 3 2"},{"iden":"sample output 2","content":"1 3 4 5 2\n\nExamples of **good permutations** include $(3, 4, 1, 5, 2)$, $(2, 4, 5, 3, 1)$, and $(4, 1, 5, 2, 3)$.\nExamples of non-**good permutations** include $(1, 2, 5, 3, 4)$, $(2, 3, 4, 1, 5)$, and $(5, 3, 1, 2, 4)$."},{"iden":"sample input 3","content":"92 4\n16 7 1 67"},{"iden":"sample output 3","content":"\\-1\n\nIf a **good permutation** does not exist, print `-1`."},{"iden":"sample input 4","content":"43 2\n43 2"},{"iden":"sample output 4","content":"\\-1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}