/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
正整数 N と長さ M の正整数列 A=(A_{1},A_{2},\dots, A_{M}) が与えられます。
ここで、 A の全ての要素は 1 以上 N 以下の整数で、相異なります。
1\leq i\leq M を満たす全ての整数 i について以下の条件を満たす、 (1, 2, \dots, N) の順列 P = (P_{1}, P_{2}, \dots, P_{N}) を 良い順列 とします。
- P のどの連続部分列も、(1, 2, \dots, A_{i}) の順列ではない。
良い順列 は存在するか判定し、存在するなら 良い順列 のうち、辞書式順序で最小のものを求めてください。
数列の辞書順とは？
数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|S|, |T| はそれぞれ S, T の長さを表します。
- |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
- ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい。
制約
- 1\leq M\leq N\leq 2\times 10^{5}
- 1\leq A_{i}\leq N
- A の要素は互いに相異なる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N M
A_{1} A_{2} \cdots A_{M}
出力
良い順列 が存在しない場合は -1 を出力してください。
存在するならば、良い順列 のうち、辞書式順序で最小のものを空白区切りで出力してください。
入力例 1
4 1 2
出力例 1
1 3 2 4
例えば (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
5 3 4 3 2
出力例 2
1 3 4 5 2
良い順列 の例として、(3,4,1,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
92 4 16 7 1 67
出力例 3
-1
良い順列 が存在しない場合は、-1 を出力してください。
入力例 4
43 2 43 2
出力例 4
-1
Score : 400 points
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.
- |S| \lt |T| and (S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|}).
- 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