Johnny 和他的朋友们一起去露营。他们想使用露营地里的木屋，这些木屋都分布在一个圆周上，彼此之间的距离不一定相等（为简单起见，我们沿圆周测量距离）。包括 Johnny 在内的每个团队成员都可以选择任意一间木屋——木屋的数量至少和团队中的人数一样多。然而，每个人都想要一些隐私，因此希望被占用的木屋之间的距离尽可能大；显然，每间木屋只能容纳一人居住。帮助他们规划假期：编写一个程序，确定要占用的木屋集合，使得它们之间的最小距离（沿圆周测量）最大。

输入格式

输入的第一行包含两个正整数 $n$ 和 $k$（$2 \le k \le n \le 500\,000$），分别表示：木屋的数量和朋友的数量（包括 Johnny）。

第二行也是最后一行包含一个由 $n$ 个正整数组成的序列 $a_i$（$1 \le a_i \le 10^9$），表示第 $i$ 号木屋与第 $i + 1$ 号木屋之间的距离（对于 $i < n$），或者第 $n$ 号木屋与第 $1$ 号木屋之间的距离（对于 $i = n$）。所有距离均沿圆周测量。

输出格式

输出一个正整数：在所有包含 $k$ 个被占用木屋的集合中，相邻被占用木屋之间的最小距离的最大值。同样，距离是沿圆周测量的。

样例

输入样例 1

5 3
1 2 5 4 3

输出样例 1

4

说明

情况如下图所示：

朋友们可以选择编号为 2、4 和 5 的木屋。此时相邻被选木屋之间的距离分别为：7、4 和 4。