题目描述

一条笔直的公路上有 $n$ 个村庄，第 $i$ 个村庄的坐标是 $x_i$，坐标可能重复。

通信公司要建 $k$ 座信号塔。塔可以建在任意位置（坐标取整数即可），每座塔的覆盖半径都相同，记为 $R$：建在坐标 $p$ 的塔可以覆盖所有满足 $|x-p|\le R$ 的村庄。

求最小的整数 $R$，使得存在一种建塔方案，让所有村庄都被覆盖。

输入格式

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

第二行 $n$ 个整数 $x_i$。

输出格式

一行一个整数，表示最小的 $R$。

输入输出样例 #1

输入 #1

5 2
1 5 9 13 17

输出 #1

4

说明

数据范围

• 对于 $100\%$ 的数据，$1\le k\le n\le 2\times 10^5$，$-10^9\le x_i\le 10^9$。