Bob 送给 Alice 一条项链作为她的生日礼物。这条项链有 $N$ 个水晶，其中 $M$ 个深得她的喜爱。形式化地，标签为 $1..N$ 的水晶按顺序串成一个圆环。而那些深得她喜爱的水晶被标记为 $n_1, n_2, \dots, n_M$。

Alice 希望将项链分成 $M$ 段。她让 Bob 将项链切成 $M$ 段。每一段都应该由原项链中连续的一段水晶组成（即水晶的标签是连续的，允许 $1$ 紧跟在 $N$ 后面），并且必须恰好包含一个深得 Alice 喜爱的水晶。显然，每个水晶必须恰好属于其中一段。

然而，切分后的项链如果有一段过长，就无法贴合 Alice 纤细的脖子。因此，她想知道，在所有满足要求的切分方案中，切分出的最长项链段的最小长度是多少。她希望你来回答这个问题。

输入格式

输入数据的第一行包含 $2$ 个整数 $N$ 和 $M$（$1 \le M \le N < 10^{18}$ 且 $M \le 10^6$）。

第二行包含 $M$ 个整数，其中第 $i$ 个整数表示 $n_i$。$n_i$ 按升序给出。

输出格式

你需要在一行中输出你的答案。

样例

输入 1

10 4
2 5 6 8

输出 1

3

说明

对于样例：你可以将项链切分为 $[1, 3], [4, 5], [6, 7], [8, 10]$。

考虑到数据规模巨大，这里提供了一种帮助快速输入的方法：

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
    for(n=0;(c=gc())<'0'||c>'9';);
    for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}