当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

信号塔

题目描述

在一条笔直的公路上有 $n$ 个村庄，第 $i$ 个村庄的坐标为 $x_i$。

现在要修建至多 $k$ 座信号塔。每座信号塔有一个相同的覆盖半径 $R$，它可以覆盖到公路上与它距离不超过 $R$ 的所有村庄。信号塔可以建在公路上的任意位置，坐标可以是实数。

请你求出最小的整数 $R$，使得至多 $k$ 座信号塔能够覆盖所有村庄。

输入格式

第一行两个整数 $n, k$，表示村庄数量和信号塔数量。

第二行 $n$ 个整数 $x_1, x_2, \dots, x_n$，表示每个村庄的坐标，保证按非降序给出。

输出格式

一个整数，表示最小的整数覆盖半径 $R$。

样例输入 1

5 2
1 2 4 7 10

样例输出 1

2

样例解释 1

当 $R=2$ 时，可以将两座信号塔放在坐标 $2$ 和 $8$ 处，分别覆盖区间 $[0,4]$ 和 $[6,10]$，覆盖所有村庄。

当 $R=1$ 时，至少需要 $4$ 座信号塔，因此不可行。

样例输入 2

3 1
0 10 20

样例输出 2

10

数据范围

• $1 \le n \le 1^5$
• $1 \le k \le n$
• $|x_i| \le 10^9$
• $x_1 \le x_2 \le \dots \le x_n$