题目描述

整数 $N$ と，長さ $K$ の単調増加な整数列 $A=(A_1,A_2,\cdots,A_K)$ が与えられます． 次の条件を満たす $(1,2,\cdots,N)$ の順列 $P$ の中で，辞書順最小のものを求めてください．

• $A$ は $P$ の最長増加部分列（単調増加な部分列であって，長さが最大のもの）である． なお，$P$ は複数の最長増加部分列を持つことがあるが，そのうちの一つが $A$ に一致していればよい．

なお，問題の制約から，条件を満たす $P$ が必ず存在することが証明できます．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_K$

输出格式

答えを出力せよ．

题目大意

[ARC125C] LIS to Original Sequence

题目描述

给定一个长度为 $k$ 的序列 $A_1,A_2,\cdots,A_n$，试求出长度为 $n$ 的序列 $P$，使得 $P$ 的最长上升子序列为 $A_1,A_2,\cdots,A_n$，且 $P$ 的字典序最小。

输入格式

第一行两个用空格隔开的整数 $n,k$。

第二行 $n$ 个整数，分别为 $A_1,A_2,\cdots,A_n$。

输出格式

用空格隔开的序列 $P$，含义如题目描述所述。

样例 #1

样例输入 #1

3 2
2 3

样例输出 #1

2 1 3

样例 #2

样例输入 #2

5 1
4

样例输出 #2

5 4 3 2 1

提示

数据范围

• $1\ \leq\ K\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_1\ <\ A_2\ <\ \cdots\ <\ A_K\ \leq\ N$
• 输入的所有值均为整数。

样例一解释

当 $P=（2，1，3）$ 或 $（2，3，1）$ 时，$P$ 的最长上升子序列与 $A$ 一样。 其中，$（2，1，3）$的字典序最小。

3 2
2 3

2 1 3

5 1
4

5 4 3 2 1

提示

制約

• $1\ \leq\ K\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_1\ <\ A_2\ <\ \cdots\ <\ A_K\ \leq\ N$
• 入力される値はすべて整数である

Sample Explanation 1

$P$ の最長増加部分列が $A$ に一致するのは，$P=(2,1,3),(2,3,1)$ のときです． このうち，辞書順最小の $(2,1,3)$ が答えになります．