C - Festival Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250 点

問題文

AtCoder 王国では、これから N 日間のお祭りが開催されます。そのうち、A_1 日目、A_2 日目、\dots、A_M 日目の 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

AtCoder 王国ではお祭りを 3 日間開催し、2,3 日目に花火が上がります。

  • 1 日目以降で初めて花火が上がるのは 2 日目なので、1 日目から数えて 1 日後です。
  • 2 日目以降で初めて花火が上がるのは 2 日目なので、2 日目から数えて 0 日後です。
  • 3 日目以降で初めて花火が上がるのは 3 日目なので、3 日目から数えて 0 日後です。

入力例 2

8 5
1 3 4 7 8

出力例 2

0
1
0
0
2
1
0
0

Score : 250 points

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