[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 $
输出格式
答えを出力せよ.
输入输出样例
输入样例 #1
3 2
2 3
输出样例 #1
2 1 3
输入样例 #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 $
- 入力される値はすべて整数である
### Sample Explanation 1
$ P $ の最長増加部分列が $ A $ に一致するのは,$ P=(2,1,3),(2,3,1) $ のときです. このうち,辞書順最小の $ (2,1,3) $ が答えになります.