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。