障碍
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

在数轴上的 区间,有 m 个障碍位于区间内的若干个整点坐标,将 区间分隔成了若干段。

如上图所示,红色表示障碍, 区间被三个障碍分隔形成了四段:,它们的长度分别为:3,3,3,1

现在可以从中移除任意多个障碍,称移除的障碍数量为 x,并称此时区间 内最长段的长度为 L

请最大化 的值,输出这个值。

输入描述:

第一行输入两个正整数 ,分别表示区间的右端点和障碍的数量。

第二行输入 m 个互不相同的正整数 以空格相隔,第 i 个正整数 a_i 表示第 i 个障碍的位置。

输出描述:

第一行输出一个整数,表示答案。
示例1

输入

复制
10 3
3 6 9

输出

复制
5

说明


移除第二个障碍 a_i=6,此时 L=9-3=6(即第一个障碍与第三个障碍之间的区间长度),x=1^2=1,答案即 6-1=5

可以发现,这是最优的情况。
示例2

输入

复制
3 3
1 2 3

输出

复制
1