102891: [Atcoder]ABC289 B - V

Problem Statement

Studying Kanbun, Takahashi is having trouble figuring out the order to read words. Help him out!

There are $N$ integers from $1$ through $N$ arranged in a line in ascending order.
Between them are $M$ "レ" marks. The $i$-th "レ" mark is between the integer $a_i$ and integer $(a_i + 1)$.

You read each of the $N$ integers once by the following procedure.

• Consider an undirected graph $G$ with $N$ vertices numbered $1$ through $N$ and $M$ edges. The $i$-th edge connects vertex $a_i$ and vertex $(a_i+1)$.
• Repeat the following operation until there is no unread integer:
  • let $x$ be the minimum unread integer. Choose the connected component $C$ containing vertex $x$, and read all the numbers of the vertices contained in $C$ in descending order.

For example, suppose that integers and "レ" marks are arranged in the following order:

(In this case, $N = 5, M = 3$, and $a = (1, 3, 4)$.)
Then, the order to read the integers is determined to be $2, 1, 5, 4$, and $3$, as follows:

• At first, the minimum unread integer is $1$, and the connected component of $G$ containing vertex $1$ has vertices $\lbrace 1, 2 \rbrace$, so $2$ and $1$ are read in this order.
• Then, the minimum unread integer is $3$, and the connected component of $G$ containing vertex $3$ has vertices $\lbrace 3, 4, 5 \rbrace$, so $5$, $4$, and $3$ are read in this order.
• Now that all integers are read, terminate the procedure.

Given $N, M$, and $(a_1, a_2, \dots, a_M)$, print the order to read the $N$ integers.

Constraints

• $1 \leq N \leq 100$
• $0 \leq M \leq N - 1$
• $1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$a_1$ $a_2$ $\dots$ $a_M$

Output

Print the answer in the following format, where $p_i$ is the $i$-th integers to read.

$p_1$ $p_2$ $\dots$ $p_N$

Sample Input 1

5 3
1 3 4

Sample Output 1

2 1 5 4 3

As described in the Problem Statement, if integers and "レ" marks are arranged in the following order:

then the integers are read in the following order: $2, 1, 5, 4$, and $3$.

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

There may be no "レ" mark.

Sample Input 3

10 6
1 2 3 7 8 9

Sample Output 3

4 3 2 1 5 6 10 9 8 7

问题描述

学习假文时，高桥不知道应该如何读取单词的顺序。 帮助他解决这个问题！

有$N$个从$1$到$N$的数字按升序排列。
在它们之间有$M$个“レ”标记。 第$i$个“レ”标记位于数字$a_i$和数字$(a_i+1)$之间。

通过以下方法读取每个数字一次。

• 考虑一个有$N$个顶点编号为$1$到$N$和$M$条边的无向图$G$。 第$i$条边连接顶点$a_i$和顶点$(a_i+1)$。
• 重复以下操作，直到没有未读数字：
  • 让$x$为最小的未读数字。 选择包含顶点$x$的图$G$的连通分量$C$，并按降序读取$C$中包含的顶点的数字。

例如，假设数字和“レ”标记按以下顺序排列：

（在这种情况下，$N = 5, M = 3$，且$a = (1, 3, 4)$。）
然后，读取数字的顺序确定为$2, 1, 5, 4$和$3$，如下所示：

• 首先，最小的未读数字是$1$，包含顶点$1$的图$G$的连通分量具有顶点$\lbrace 1, 2 \rbrace$，因此按此顺序读取$2$和$1$。
• 然后，最小的未读数字是$3$，包含顶点$3$的图$G$的连通分量具有顶点$\lbrace 3, 4, 5 \rbrace$，因此按此顺序读取$5, 4$和$3$。
• 现在所有数字都已读取，终止程序。

给定$N, M$和$(a_1, a_2, \dots, a_M)$，按顺序打印要读取的$N$个数字。

约束条件

• $1 \leq N \leq 100$
• $0 \leq M \leq N - 1$
• $1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1$
• 输入中的所有值都是整数。

输入

输入从标准输入按以下格式给出：

$N$ $M$
$a_1$ $a_2$ $\dots$ $a_M$

输出

按以下格式打印答案，其中$p_i$是要读取的第$i$个数字。

$p_1$ $p_2$ $\dots$ $p_N$

样例输入1

5 3
1 3 4

样例输出1

2 1 5 4 3

如问题描述中所述，如果数字和“レ”标记按以下顺序排列：

则数字按以下顺序读取：$2, 1, 5, 4$和$3$。

样例输入2

5 0

样例输出2

1 2 3 4 5

可能没有“レ”标记。

样例输入3

10 6
1 2 3 7 8 9

样例输出3

4 3 2 1 5 6 10 9 8 7