题目描述

对于给定的一个长度为 N 的正整数数列 a[1..N]，内容本身已经有序，数列为递增序列。现要往数列中插入 M 个数，要求插入数字之后数列依然保持递增形态，并且要求相邻数项之间差值的最大值的最小值。

关于相邻数项查找的最大值，下面有几个例子：

一数列 {11,24,67,92,97} 要插入 3 个数字。

如果插入数字 17, 45, 69 ，新数列为：{11,17,24,45,67,69,79,97} ,则新数列的相邻数项差为：{6,7,21,22,2,10,18} ，最大值为 22 。

如果插入数字 46, 80, 94 ，新数列为：{11,24,46,67,80,92,94,97} ,则新数列的相邻数项差为：{13,23,21,13,12,2,3}，最大值为 23 。

如果插入 39, 54, 80，如果新数列为：{11,24,39,54,67,80,92,97} ,则新数列相邻项的差为 {13,15,15,13,13,12,2}，最大值为 15 。

并且无论如何分段，差值的最大值不会小于 15 。

所以在数列 {11,24,67,92,97} 中插入 3 个数字，新数列相邻数项的差的最大值的最小值为 15 （也就是说差的最大值不小于 15 ）。

数据范围

对于 100% 的数据，1≤ N≤ $10^5$ , $a_i$ ≤ $10^8$

输入格式

第 1 行包含两个正整数 N , M 。

第 2 行包含 N 个空格隔开的非负整数 $a_i$，含义如题目所述。

输出格式

一个正整数，新数列相邻项的差的最大值的最小值。

样例

5 3
11 24 67 92 97

15