← 返回题目列表

AtCoder · arc125_c

C. LIS 到原始序列

中文机器翻译题面 查看原题

分数: 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