题目描述

一条直线上有 $n$ 个候选位置，第 $i$ 个位置的坐标为 $x_i$，所有坐标互不相同。需要从中选择恰好 $k$ 个位置安装信号站。

定义方案的安全间距为任意两个已选信号站之间距离的最小值。请使安全间距尽可能大，并输出最大值。

输入格式

第一行输入两个整数 $n,k$。

第二行输入 $n$ 个互不相同的整数 $x_1,x_2,\ldots,x_n$。输入顺序不保证有序。

输出格式

输出能够得到的最大安全间距。

样例

5 3
10 1 2 7 14

6

数据规模与约定

• $2\le k\le n\le2\times10^5$；
• $0\le x_i\le10^9$；
• 所有 $x_i$ 互不相同。