Score : $400$ points

问题陈述

给定一个正整数 $N$ 和一个包含 $M$ 个正整数的序列 $A = (A_{1}, A_{2}, \dots, A_{M})$。

这里，$A$ 中的所有元素都是 $1$ 到 $N$（包括两端）之间的不同整数。

如果一个排列 $P = (P_{1}, P_{2}, \dots, P_{N})$ 满足以下条件，对于所有整数 $i$ 满足 $1 \leq i \leq M$：

• $P$ 的任意连续子序列都不是 $(1, 2, \dots, A_{i})$ 的排列。

则称这个排列为 好排列。

确定是否存在一个 好排列，如果存在，找到字典序最小的 好排列。

什么是字典序？

如果满足以下条件之一，则称序列 $S = (S_1, S_2, \ldots, S_{|S|})$ 字典序小于序列 $T = (T_1, T_2, \ldots, T_{|T|})$。这里，$|S|$ 和 $|T|$ 分别表示 $S$ 和 $T$ 的长度。

1. $|S| \lt |T|$ 且 $(S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|})$。
2. 存在一个整数 $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ 满足以下两个条件：
   • $(S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})$。
   • $S_i$ 数字上小于 $T_i$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a positive integer $N$ and a sequence of $M$ positive integers $A = (A_{1}, A_{2}, \dots, A_{M})$.

Here, all elements of $A$ are distinct integers between $1$ and $N$, inclusive.

A 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$:

• No contiguous subsequence of $P$ is a permutation of $(1, 2, \dots, A_{i})$.

Determine whether a good permutation exists, and if it does, find the lexicographically smallest good permutation.

What 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.

1. $|S| \lt |T|$ and $(S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|})$.
2. There exists an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that both of the following hold:
   • $(S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})$.
   • $S_i$ is smaller than $T_i$ (as a number).

Constraints

• $1 \leq M \leq N \leq 2 \times 10^{5}$
• $1 \leq A_{i} \leq N$
• All elements of $A$ are distinct.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_{1}$ $A_{2}$ $\cdots$ $A_{M}$

Output

If a good permutation does not exist, print -1.

If it exists, print the lexicographically smallest good permutation, separated by spaces.

Sample Input 1

4 1
2

Sample Output 1

1 3 2 4

For example, $(4, 2, 1, 3)$ is not a good permutation because it contains $(2, 1)$ as a contiguous subsequence.

Other non-good permutations are $(1, 2, 3, 4)$ and $(3, 4, 2, 1)$.

Some 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.

Sample Input 2

5 3
4 3 2

Sample Output 2

1 3 4 5 2

Examples of good permutations include $(3, 4, 1, 5, 2)$, $(2, 4, 5, 3, 1)$, and $(4, 1, 5, 2, 3)$.

Examples of non-good permutations include $(1, 2, 5, 3, 4)$, $(2, 3, 4, 1, 5)$, and $(5, 3, 1, 2, 4)$.

Sample Input 3

92 4
16 7 1 67

Sample Output 3

-1

If a good permutation does not exist, print -1.

Sample Input 4

43 2
43 2

Sample Output 4

-1