题目描述

疫情时期公共场合需要保持社交距离。

小布家楼下有个餐厅叫肯当劳，里面有 $n$ 个座位排成直线，可以用坐标描述这些座位的位置，分别为 $x_1,x_2,\dots,x_n$。

现在有 $k$ 个顾客同时需要用餐，请你帮忙选出相应的座位，使得选出的座位两两之间的最短距离尽可能大，计算该最短距离的最大值。

输入格式

共两行：
第一行两个整数 $n,k$；
第二行 $n$ 个整数 $x_1,x_2,\dots,x_n$。

输出格式

一个整数，表示要求的最大值。

输入输出样例 #1

输入 #1

5 3
3 2 1 4 5

输出 #1

2

说明/提示

数据范围

对于 $30\%$ 的数据，$1 \leq n \leq 12$，$-10^3\leq x_i \leq 10^3$；
对于 $60\%$ 的数据，$1 \leq n \leq 500$，$-10^6\leq x_i \leq 10^6$；
对于 $100\%$ 的数据，$1 \leq n \leq 3\times 10^5$，$-10^9\leq x_i\leq 10^9$, $k\le n$。