路由器最大间距

题目描述

从n个互不相同的整数位置中选择c个放置路由器。位置先按升序理解，最大化相邻已选路由器之间的最小距离。

输入格式

第一行输入n、c；第二行输入n个互不相同的位置，保证2≤c≤n。

输出格式

输出最大可能的最小距离。

数据范围

• $2 \le c \le n \le 2\times 10^5$；
• 所有位置互不相同，且 $-10^9 \le x_i \le 10^9$。

样例

输入

5 3
1 2 8 4 9

输出

3