AT_abc322_c [ABC322C] Festival

题目描述

在 AtCoder 王国，将举办为期 $N$ 天的庆典。在这期间，第 $A_1$ 天、第 $A_2$ 天、$\dots$、第 $A_M$ 天这 $M$ 天会燃放烟花。这里保证在庆典的最后一天会燃放烟花（即 $A_M = N$ 保证成立）。

请你对于 $i=1,2,\dots,N$，回答以下问题：

• 从第 $i$ 天起，距离下次（含当天）烟花燃放还有几天？如果第 $i$ 天就有烟花，则为 $0$ 天。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$

输出格式

输出 $N$ 行。

第 $i$ 行输出从第 $i$ 天起距离下次烟花燃放还有几天，作为一个整数输出。

输入输出样例 #1

输入 #1

3 2
2 3

输出 #1

1
0
0

输入输出样例 #2

输入 #2

8 5
1 3 4 7 8

输出 #2

0
1
0
0
2
1
0
0

说明/提示

限制条件

• $1 \leq M \leq N \leq 2 \times 10^5$
• $1 \leq A_1 < A_2 < \dots < A_M = N$
• 输入均为整数

样例解释 1

在 AtCoder 王国，庆典举办 $3$ 天，第 $2$ 天和第 $3$ 天有烟花。

• 从第 $1$ 天起，最近的烟花在第 $2$ 天，所以距离为 $1$ 天。
• 从第 $2$ 天起，最近的烟花就在当天，所以距离为 $0$ 天。
• 从第 $3$ 天起，最近的烟花就在当天，所以距离为 $0$ 天。

由 ChatGPT 4.1 翻译