AT_abc301_b [ABC301B] Fill the Gaps

题目描述

有一个长度为 $N$ 的正整数数列 $A=(A_1,\ldots,A_N)$。任意相邻的两个元素都不相等。

对于这个数列，按照以下操作插入一些数：

1. 如果数列 $A$ 的所有相邻两项的差的绝对值都是 $1$，则操作结束。
2. 从数列 $A$ 的开头开始，找到第一个相邻两项的差的绝对值不是 $1$ 的位置，记为 $A_i,A_{i+1}$。
   • 如果 $A_i < A_{i+1}$，则在 $A_i$ 和 $A_{i+1}$ 之间插入 $A_i+1,A_i+2,\ldots,A_{i+1}-1$。
   • 如果 $A_i > 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$

输出格式

请将操作结束后的数列的每个元素用空格分隔输出。

输入输出样例 #1

输入 #1

4
2 5 1 2

输出 #1

2 3 4 5 4 3 2 1 2

输入输出样例 #2

输入 #2

6
3 4 5 6 5 4

输出 #2

3 4 5 6 5 4

说明/提示

限制条件

• $2 \leq N \leq 100$
• $1 \leq A_i \leq 100$
• $A_i \neq A_{i+1}$
• 输入均为整数

样例解释 1

最初，数列为 $(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)$。

样例解释 2

有时一次也不需要插入。

由 ChatGPT 4.1 翻译