[ARC125C] LIS to Original Sequence

# [ARC125C] LIS to Original Sequence ## 题目描述 [problemUrl]: https://atcoder.jp/contests/arc125/tasks/arc125_c 给定一个长度为 $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）$的字典序最小。

[problemUrl]: https://atcoder.jp/contests/arc125/tasks/arc125_c 整数 $ 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 $

答えを出力せよ．

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) $ が答えになります．