4152. 弑王之剑

【题目背景】

浮生梦，三生渺渺，因缘无踪，虽堪恋，何必重逢。息壤生生，谁当逝水，东流无终。

People come and go, we struggled with laughter and tears,and all the years have gone by,still I have you by my side.

或许是不知梦的缘故,流离之人追逐幻影。

凡王之血，必以剑终！

【题目描述】

现在你有 $n$ 把剑，每把剑都有一个力量值 $a_i$，有一个锻造师对这些剑锻造了 $m$ 次。

每次锻造，锻造师都会将第 $k$ 把剑的力量值即 $a_k$ 设置为 $n$，同时这把剑还会影响其他的剑。具体的，对于第 $i$ 把剑，其力量值变为 $a_i=a_k-|i-k|$，其中 $i$ 不等于 $k$。

请你告诉锻造师，$m$ 次锻造之后，每把剑的低谷力量值即 $m$ 次锻造中最小的力量值是多少。

【输入格式】

一行两个正整数 $n,m$，代表剑的总个数为 $n$，锻造总次数为 $m$ 个。

接下来一行有 $m$ 个正整数。对于第 $i$ 个正整数，代表第 $i$ 次锻造更改第 $k$ 把剑的力量值为 $n$。

【输出格式】

一行 $n$ 个整数，代表 $m$ 次锻造后第 $i$ 把剑的低谷力量值，即 $\min a_i$。

【样例1输入】

5 5
2 4 3 5 3

【样例1输出】

1 2 3 3 2

【样例2输入】

10 10
9 2 5 2 8 7 5 9 4 9

【样例2输出】

2 3 4 5 6 6 5 4 3 2

【样例3输入】

15 15
8 5 7 8 9 5 1 1 4 2 3 8 4 14 6

【样例3输出】

2 3 4 5 6 7 8 8 7 6 5 4 3 2 1

【样例4输入】

20 20
5 2 1 11 11 3 3 8 5 19 2 1 2 5 9 3 10 4 19 13

【样例4输出】

2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1

在此键入。

【数据规模与约定】

对于 $60\%$ 的数据， $1 \leq n,m \leq 10^4$ 。

对于剩下的 $40\%$ 的数据， $1 \leq n,m \leq 10^5$ 。

对于全部的数据，保证 $1 \leq n,m \leq 10^5,1 \leq k \leq n$。

【来源】

校际联合邀请赛第6场语法组T3