题目描述

B 市和 T 市之间有一条长度为 $L$ 的高速公路，公路上已经设置了 $N$ 个路标。

我们把所有相邻路标之间距离的最大值，称为这条公路的“空旷指数”。

现在政府最多可以在公路上新增 $K$ 个路标，希望通过合理设置新路标的位置，使公路的“空旷指数”尽可能小。

公路的起点和终点已经保证设有路标。公路长度为整数，并且原有路标和新设置的路标都必须位于距离起点整数个单位的位置。

请计算最多新增 $K$ 个路标后，可以得到的最小“空旷指数”。

输入格式

第一行输入三个整数 $L$、$N$、$K$，分别表示公路的长度、原有路标的数量以及最多可以新增的路标数量。

第二行输入 $N$ 个严格递增的整数，表示原有路标的位置。

路标的位置使用其距离公路起点的距离表示，并且均位于区间 $[0,L]$ 内。

保证公路的起点 $0$ 和终点 $L$ 均已设置路标。

输出格式

输出一个整数，表示最多新增 $K$ 个路标后，可以达到的最小“空旷指数”。

样例

101 2 1
0 101

51

样例解释

公路原来只在起点和终点处设置了两个路标，两者之间的距离为 $101$。

现在最多可以新增一个路标。可以将新路标设置在距离起点 $50$ 或 $51$ 个单位的位置。

此时相邻路标之间的最大距离均为 $51$，因此能够达到的最小“空旷指数”为 $51$。

数据范围

对于 $50$ 的测试数据：

$2 \le N \le 100$。

$0 \le K \le 100$。

对于 $100$ 的测试数据：

$2 \le N \le 100000$。

$0 \le K \le 100000$。

$0 < L \le 10000000$。

来源：洛谷P3853