AT_arc178_a [ARC178A] Good Permutation 2

[problemUrl]: https://atcoder.jp/contests/arc178/tasks/arc178_a 正整数 $ 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 $ の長さを表します。 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 $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ (S_1,S_2,\ldots,S_{i-1})\ =\ (T_1,T_2,\ldots,T_{i-1}) $ - $ S_i $ が $ T_i $ より（数として）小さい。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ A_{1} $ $ A_{2} $ $ \cdots $ $ A_{M} $

**良い順列** が存在しない場合は `-1` を出力してください。 存在するならば、**良い順列** のうち、辞書式順序で最小のものを空白区切りで出力してください。

### 制約 - $ 1\leq\ M\leq\ N\leq\ 2\times\ 10^{5} $ - $ 1\leq\ A_{i}\leq\ N $ - $ A $ の要素は互いに相異なる - 入力は全て整数 ### Sample Explanation 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) $ なので、これを空白区切りで出力してください。 ### Sample Explanation 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) $ があります。 ### Sample Explanation 3 \*\*良い順列\*\* が存在しない場合は、`-1` を出力してください。