分数: 600 点
问题陈述
给定一个整数 N 和单调递增序列 K 整数 A=(A_1,A_2,\cdots,A_K)。 找到 字典顺序最小 排列 P of (1,2,\cdots,N) 满足以下条件。
- A 是最长递增子序列 P (单调递增子序列 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
A 是最长递增子序列 P 当 P=(2,1,3),(2,3,1)。 答案是两者中字典顺序最小的一个,或者 (2,1,3).
示例输入 2
5 1 4
示例输出 2
5 4 3 2 1