Score : $250$ points

问题描述

AtCoder王国举行了一个持续 $N$ 天的节日。在这其中的 $M$ 天，即第 $A_1$ 天、第 $A_2$ 天、……、第 $A_M$ 天将会燃放烟花。保证在节日的最后一天一定会燃放烟花。（换句话说，可以确保 $A_M=N$。）

对于每个 $i=1,2,\dots,N$，解决以下问题：

• 从第 $i$ 天开始算起，首次在第 $i$ 天或之后燃放烟花需要等待多少天？如果在第 $i$ 天就燃放了烟花，则视为等待 $0$ 天。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

The AtCoder Kingdom holds a festival for $N$ days. On $M$ of these days, namely on the $A_1$-th, $A_2$-th, $\dots$, $A_M$-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, $A_M=N$ is guaranteed.)

For each $i=1,2,\dots,N$, solve the following problem.

• How many days later from the $i$-th day will fireworks be launched for the first time on or after the $i$-th day? If fireworks are launched on the $i$-th day, it is considered to be $0$ days later.

Constraints

• $1 \le M \le N \le 2 \times 10^5$
• $1 \le A_1 < A_2 < \dots < A_M = N$
• All input values 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 $N$ lines.

The $i$-th line $(1 \le i \le N)$ should contain an integer representing the number of days from the $i$-th day until fireworks are launched for the first time on or after the $i$-th day.

Sample Input 1

3 2
2 3

Sample Output 1

1
0
0

The kingdom holds a festival for $3$ days, and fireworks are launched on the $2$-nd and $3$-rd days.

• From the $1$-st day, the first time fireworks are launched is the $2$-nd day of the festival, which is $1$ day later.
• From the $2$-nd day, the first time fireworks are launched is the $2$-nd day of the festival, which is $0$ days later.
• From the $3$-rd day, the first time fireworks are launched is the $3$-rd day of the festival, which is $0$ days later.

Sample Input 2

8 5
1 3 4 7 8

Sample Output 2

0
1
0
0
2
1
0
0

update @ 2024/3/10 01:42:21