思路：二分

随着种树区间的增长，公路上被种上的树的数量单调不降，具有单调性，因此可以使用二分解决。

二分种树区间长度，并$O(N)$扫一遍工人的种树区间，判断能否种上$k$棵树，能就减少二分长度，否则增大二分长度。

题目内容

​ 长度无限长的公路上，小美雇佣了$n$位工人来种树，每个点最多种一棵树。

从左向右数，工人所站的位置为$a_1,a_2,...,a_n$。已知每位工人都会将自己所在位置的右侧一段长度的区间种满树，且每位工人的种树区间长度相同。

现在小美希望公路上至少有$k$棵树，为了节约成本，他希望每位工人种树的区间长度尽可能短，请你帮他求出，工人们的种树区间至少多长，从能使得公路被种上至少$k$棵树。

输入描述

第一行输入两个正整数$n$，$k$($1≤n,k≤2×10^5$),分别为表示工人的数量，以及小美要求树的最少数量。

第二行输入$n$个正整数$a_1,a_2,...,a_n$($1≤a_i≤2×10^5$),表示每名工人的位置。

输出描述

在一行输出一个整数，代表工人们最短的种树区间长度。

样例1

输入

3 6
1 2 5

输出

3

说明

每位工人种树的区间长度至少为$3$。

这样以来：

第一名工人种：$1,2,3$点的树。

第二名工人种：$2,3,4$点的树。

第三名工人种：$5,6,7$点的树。

由于每个位置最多种一棵树，因此共有：$1,2,3,4,5,6,7$这些点有树，满足至少$k=6$棵树