/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
整数 N と，長さ K の単調増加な整数列 A=(A_1,A_2,\cdots,A_K) が与えられます． 次の条件を満たす (1,2,\cdots,N) の順列 P の中で，辞書順最小のものを求めてください．
- A は P の最長増加部分列（単調増加な部分列であって，長さが最大のもの）である． なお，P は複数の最長増加部分列を持つことがあるが，そのうちの一つが A に一致していればよい．
なお，問題の制約から，条件を満たす P が必ず存在することが証明できます．
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_1 < A_2 < \cdots < A_K \leq N
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N K A_1 A_2 \cdots A_K
出力
答えを出力せよ．
入力例 1
3 2 2 3
出力例 1
2 1 3
P の最長増加部分列が A に一致するのは，P=(2,1,3),(2,3,1) のときです． このうち，辞書順最小の (2,1,3) が答えになります．
入力例 2
5 1 4
出力例 2
5 4 3 2 1
Score : 600 points
Problem Statement
Given are an integer N and a monotonically increasing sequence of K integers A=(A_1,A_2,\cdots,A_K). Find the lexicographically smallest permutation P of (1,2,\cdots,N) that satisfies the following condition.
- A is a longest increasing subsequence of P (a monotonically increasing subsequence of P with the maximum possible length). It is fine if P has multiple longest increasing subsequences, one of which is A.
From the Constraints of this problem, we can prove that there always exists a P that satisfies the condition.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_1 < A_2 < \cdots < A_K \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \cdots A_K
Output
Print the answer.
Sample Input 1
3 2 2 3
Sample Output 1
2 1 3
A is a longest increasing subsequence of P when P=(2,1,3),(2,3,1). The answer is the lexicographically smallest of the two, or (2,1,3).
Sample Input 2
5 1 4
Sample Output 2
5 4 3 2 1