103222: [Atcoder]ABC322 C - Festival

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

问题描述

AtCoder王国将举办一个持续$N$天的节日。在其中的$M$天，即第$A_1$天、第$A_2$天、$\dots$、第$A_M$天将燃放烟花。保证在节日的最后一天会燃放烟花。（换句话说，保证$A_M=N$。）

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

• 从第$i$天开始，烟花会在多少天后首次在第$i$天或之后燃放？如果在第$i$天燃放烟花，那么认为是$0$天后。

约束条件

• $1 \le M \le N \le 2 \times 10^5$
• $1 \le A_1 < A_2 < \dots < A_M = N$
• 所有输入值都是整数。

输入

输入通过标准输入给出，格式如下：

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

输出

输出$N$行。

第$i$行 $(1 \le i \le N)$ 应包含一个整数，表示从第$i$天开始到烟花首次在第$i$天或之后燃放的天数。

样例输入1

3 2
2 3

样例输出1

1
0
0

王国将举办一个持续$3$天的节日，烟花将在第$2$天和第$3$天燃放。

• 从第$1$天开始，烟花首次在节日的第$2$天燃放，这是一天后。
• 从第$2$天开始，烟花首次在节日的第$2$天燃放，这是$0$天后。
• 从第$3$天开始，烟花首次在节日的第$3$天燃放，这是$0$天后。

样例输入2

8 5
1 3 4 7 8

样例输出2

0
1
0
0
2
1
0
0