Description

新冠疫情，导致了各个城市之间物资输送的障碍。假设有$N$ 个城市在一条直线上，为了物资能顺利抵达各个城市，可以在路线上建立最多个数为K个暂时停靠站，由于火车在两个站台（城市也算站台）之间的距离越近，需要的总花费越少，因此我们需要让火车相邻两个站台之间的最大距离最小，求出距离 $L$, $2 ≤ N ≤ 100000, 0 \le k \le 100000$，所有城市坐标小于等于 $10^{12}$，且不存在负值。提醒： 城市坐标均为正整数，且停靠站只能建在整数坐标点上。

Input Format

第一行输入城市个数N，可建立停靠站个数K， 第二行输入N个城市的坐标（不保证前一个城市坐标比后一个城市小）。

Output Format

输出L

2 2
4 106​

34​

Source

二分答案