AT_arc178_a [ARC178A] Good Permutation 2

给定一个正整数 $N$ 和一个长度为 $M$ 的正整数序列 $A=(1,2,\cdots,A_M)$。 其中，$A$ 中的所有元素都是介于 $1$ 和 $N$ 之间的不同整数。（即 $A$ 是 $N$ 的一个排列） 定义： - 排列 $P=(P_1,P_2,\cdots,P_N)$ 是一个**好排列**，当且仅当：$P$ 没有连续子序列是 $A=(1,2,⋯ ,A_i)$ 的排列，其中 $1\le i\le M$。 确定是否存在这样的**好排列**，如果存在，找到**字典序最小**的好排列。

第一行两个整数 $N,M$。 第二行 $M$ 个整数 $A_{1},A_{2},\cdots,A_{M}$。

如果不存在好排列，则输出 `-1`。 如果存在，输出**字典序最小**的好排列，每个数之间用空格分隔。 ## 样例 #1 ### 样例输入 #1 ``` 4 1 2 ``` ### 样例输出 #1 ``` 1 3 2 4 ``` ## 样例 #2 ### 样例输入 #2 ``` 5 3 4 3 2 ``` ### 样例输出 #2 ``` 1 3 4 5 2 ``` ## 样例 #3 ### 样例输入 #3 ``` 92 4 16 7 1 67 ``` ### 样例输出 #3 ``` -1 ``` ## 样例 #4 ### 样例输入 #4 ``` 43 2 43 2 ``` ### 样例输出 #4 ``` -1 ```

- $ 1\leq\ M\leq\ N\leq\ 2\times\ 10^{5} $ - $ 1\leq\ A_{i}\leq\ N $ - $ A $ 中的所有元素都是不同的。 - 所有输入值都是整数。 ### 样例解释1 例如，$(4,2,1,3)$ 不是一个 好排列，因为它包含 $(2,1)$ 作为连续子序列。 其他非好排列包括 $(1,2,3,4)$ 和 $(3,4,2,1)$。 一些好排列包括 $(4,1,3,2)$ 和 $(2,3,4,1)$。其中，字典序最小的排列是 $(1,3,2,4)$。 ### 样例解释2 好排列的示例包括 $(3,1,4,5,2)$、$(2,4,5,3,1)$ 和 $(4,1,5,2,3)$。 非好排列的示例包括 $(1,2,5,3,4)$、$(2,3,4,1,5)$ 和$(5,3,1,2,4)$。 ### 样例解释3 不存在好排列，输出 `-1`。