F-音游家的谱面(Hard version)

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

（本题和Easy version的区别仅在数据范围不同）

牛牛最近在玩一款叫做牛特斯的下落式音游，下落式音游是一种音乐节拍类游戏，在屏幕上平行分布若干条轨道，音符在这些轨道上移动。

当音符与屏幕底部的判定线重合时点击音符即可命中。对于有 ${N}$ 条轨道的音游被称之为是一个 ${N}$ Key音游，例如常见的4 Key音游，5 Key音游，8 Key音游。

在一轮游戏中共有 ${M}$ 个音符，对于每一个音符，都有两个属性 ${pos_i}$ 和 ${time_i}$ ， ${pos_i}$ 为正整数，表示音符下落时所属的轨道为 ${pos_i}$ ， ${time_i}$ 是一个实数，表示音符到达判定线的时间为 ${time_i}$ 毫秒，由于 ${time_i}$ 是一个实数，同时出现的音符被理解成间隔非常小的时间单位，所以允许音符同时出现。

游玩这类音游时，一般人会使用两只手，或者两只拇指，并且游戏开始时左手放在1号轨道，右手放在第 ${N}$ 号轨道。在第 ${i}$ 毫秒中（第 ${i}$ 毫秒中指 ${[i,i+1)}$ 这段时间区间，左闭右开），如果两只手分别放在 ${x}$ 和 ${y}$ 这两个位置上，那么理论上就可以命中在第i毫秒中轨道 ${x}$ 和 ${y}$ 上到达判定线的所有音符。（当然，如果你技术够好的话）

在每一毫秒末，两只手可以独立的各自进行移动，但是只能移动到它们相邻的轨道上。具体来讲，假设左右手在第 ${i}$ 毫秒中位于 ${x}$ 和 ${y}$ 这两个位置上，记为 ${(x,y)}$ 。那么在第 ${i}$ 毫秒末，共有9种不同的移动方案，即 ${(x-1,y-1),(x,y-1),(x+1,y-1),(x-1,y),(x,y),(x+1,y),(x-1,y+1),(x,y+1),(x+1,y+1)}$ 。

在音游中，有一些谱面由于过度反人类，不适合人类游玩而被称为是“粪谱”。
具体来讲，如果假设一开始左手在第 ${1}$ 号轨道，右手在第 ${N}$ 号轨道，双手各自独立的按照上述规则，每毫秒末移动一个单位。不存在任何一种方案可以在理论上全部命中的 ${M}$ 个音符，就称这个谱面是一个“粪谱”。

我们称最后一个音符，即第 ${M}$ 个音符到达判定线的时间为整个谱面的时长。

现在给你这 ${M}$ 个音符按照时间顺序的轨道坐标 ${pos_i}$ ，请你设计一个谱面时长最小的非“粪谱”谱面。
也就是说你需要给出这 ${M}$ 个音符到达判定线的时间 ${time_i}$ ，并且要求 $time_1 \leq time_2 \leq ... \leq time_M$ ， ${time_i}$ 可以为实数，但是为了避免一些不必要的精度问题，你只需要输出 $\left \lfloor time_i \right \rfloor$ 即可。

当然，符合条件的谱面不唯一，你只用输出任意一种符合题目要求的即可。

输入描述:

第一行输入两个正整数，表示音游的轨道数目和音符数。

接下来一行个正整数，表示这个音符按照时间顺序出现的轨道编号。

输出描述:

输出一行，表示每个音符到达判定线的时间向下取整后的结果。

示例1

输入

复制

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

输出

复制

0 1 2 3 4 4 5 6 7 8

说明

10 Key音游，共有10个下落音符，并且按照时间顺序分别出现在1~10号轨道。
其中一种谱面时长最小的非“粪谱”谱面可以是：












在第毫秒即这段时间内，左手在，右手在，左手敲击第个音符，然后在第毫秒末，左手向右移动一个轨道，同时右手向左移动一个轨道。
在第毫秒即这段时间内，左手在，右手在，左手敲击第个音符，然后在第毫秒末，左手向右移动一个轨道，同时右手向左移动一个轨道。
在第毫秒即这段时间内，左手在，右手在，左手敲击第个音符，然后在第毫秒末，左手向右移动一个轨道，同时右手向左移动一个轨道。
在第毫秒即这段时间内，左手在，右手在，左手敲击第个音符，然后在第毫秒末，左手向右移动一个轨道，同时右手向左移动一个轨道。
在第毫秒即这段时间内，左手在，右手在，左右手同时敲击第、个音符，然后在第毫秒末，右手向右移动一个轨道，左手原地摸鱼。
在第毫秒即这段时间内，左手在，右手在，右手敲击第个音符，然后在第毫秒末，右手向右移动一个轨道，左手继续摸鱼。
在第毫秒即这段时间内，左手在，右手在，右手敲击第个音符，然后在第毫秒末，右手向右移动一个轨道，左手继续摸鱼。
在第毫秒即这段时间内，左手在，右手在，右手敲击第个音符，然后在第毫秒末，右手向右移动一个轨道，左手继续摸鱼。
在第毫秒即这段时间内，左手在，右手在，右手敲击第个音符，游戏结束，谱面总用时共毫秒。

示例2

输入

复制

1000 6
1 1000 1 1000 1 1000

输出

复制

0 0 0 0 0 0

说明

由于是一个实数，同时出现的音符被理解成间隔非常小的时间单位，所以允许音符同时出现。
一开始左手在，右手在。然后因为都很小，。你不用很关心它们的值具体是多少，只用知道是个很小的数然后输出即可。

示例3

输入

复制

4 10
1 4 2 3 4 1 3 2 1 4

输出

复制

0 0 1 1 2 2 3 3 4 4

说明

注意题目要求，要保证是非“粪谱”并且音符到达判定线的时间满足。

示例4

输入

复制

100 2
98 10

输出

复制

9 9

说明

答案不唯一
2 9
3 9
4 9
...
9 9
都是符合题目要求的解