填补空缺

题目描述

我们有一个由正整数组成、长度为 $N$ 的数列 $A=(A_1,\ldots,A_N)$。任意两个相邻的项取值不同。

按下述操作向该数列中插入一些数。

1. 若数列 $A$ 中任意相邻两项的差的绝对值都为 $1$,则终止操作。
2. 令 $A_i, A_{i+1}$ 为从数列 $A$ 的开头数起、差的绝对值不为 $1$ 的第一对相邻项。
   • 若 $A_i \lt A_{i+1}$,则在 $A_i$ 和 $A_{i+1}$ 之间插入 $A_i+1,A_i+2,\ldots,A_{i+1}-1$。
   • 若 $A_i \gt A_{i+1}$,则在 $A_i$ 和 $A_{i+1}$ 之间插入 $A_i-1,A_i-2,\ldots,A_{i+1}+1$。
3. 返回步骤 1。

输出操作终止时的数列。

输入格式

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

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出操作终止时的数列的各个元素,以空格分隔。

样例

4
2 5 1 2

2 3 4 5 4 3 2 1 2

初始数列为 $(2,5,1,2)$。操作过程如下。

• 在第 1 项的 $2$ 和第 2 项的 $5$ 之间插入 $3,4$,数列变为 $(2,3,4,5,1,2)$。
• 在第 4 项的 $5$ 和第 5 项的 $1$ 之间插入 $4,3,2$,数列变为 $(2,3,4,5,4,3,2,1,2)$。

6
3 4 5 6 5 4

3 4 5 6 5 4

也可能一次插入都不会进行。

数据范围

• $2 \le N \le 100$
• $1 \le A_i \le 100$
• $A_i \neq A_{i+1}$
• 输入中的所有值均为整数。