You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1163 题。

题目描述

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

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

输入格式

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

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

输出格式

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

样例

8 3
3 6 2

5 3 3

说明/提示

$1 \le x \le 10^9,1 \le n \le 2\cdot 10^5,0 < p_i < x$。