P3853 路标设置

题目背景

B市和T市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，管理部门提出了"空旷指数"的概念。

定义"空旷指数"为公路上相邻两个路标之间距离的最大值。

现在已知这条公路总长度为 $L$ ，原有 $N$ 个路标（路标位置已按递增顺序给出），并且计划在这条公路上最多增设 $K$ 个新的路标。

增设路标后，"空旷指数"会发生变化。请计算增设不超过 $K$ 个路标后，能够达到的最小"空旷指数"是多少。

第 1 行包括三个数 $L$ ， $N$ ， $K$ ，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。

第 2 行包括递增排列的 $N$ 个整数，分别表示原有的 $N$ 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 $[0, L]$ 内。

输出 1 行，包含一个整数，表示增设路标后能达到的最小"空旷指数"值。

100 2 1
0 50

原有路标在位置 0 和 50，空旷指数为 50。增设 1 个路标后，最优方案是在位置 25 或 75 设置新路标，使得相邻路标间距离最大为 25，即最小"空旷指数"为 25。

对于 $100\%$ 的数据，保证 $1\le L\le 10^6$ ， $0\le N\le 10^5$ ， $0\le K\le 10^5$ 。