链接: https://cses.fi/problemset/task/1163

板块: Sorting and Searching

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有一条长度为 $x$ 的街道，位置编号为 $0,1,\ldots,x$。最初街道上没有交通灯，但随后会逐个加入 $n$ 组交通灯。

你的任务是在每次加入后，计算不含交通灯的最长路段的长度。

输入

第一行包含两个整数 $x$ 和 $n$：街道长度和交通灯组数。

接下来一行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$：每组交通灯的位置。每个位置互不相同。

输出

输出每次加入后不含交通灯的最长路段长度。

数据范围

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

样例输入

8 3
3 6 2

样例输出

5 3 3