题目描述

有一条长度为 $x$ 的街道，为了简单起见，街道可以看成是长为 $x$ 的数轴，数轴上有编号为 $0, 1, \ldots, x$ 共 $x + 1$ 个点。街道上最初没有红绿灯，后来陆续增加了 $n$ 组红绿灯。

你的任务是计算每次增加红绿灯后没有红绿灯的最长通道的长度。

输入格式

第一行包含两个整数 $x$ 和 $n$，分别代表街道长度和交通信号灯组数。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$，分别代表每组交通信号灯的位置（即数轴上的位置）。每个位置都是不同的。

输出格式

输出 $n$ 个整数，表示每次添加后不带红绿灯的最长通道的长度。

样例

8 3
3 6 2

5 3 3

数据范围

• $1 \le x \le 10^9$
• $1 \le n \le 2 \times 10^5$
• $0 < p_i < x$