题目描述

一年一度的“跳石头”比赛又要开始了！

比赛在一条笔直的河道中进行，河道中分布着一些岩石。组委会选择了起点和终点两块岩石作为比赛的开始与终点。起点和终点之间共有 N 块岩石（不含起点和终点的岩石）。参赛者从起点出发，每一步跳到相邻的一块岩石，直到到达终点。

为了增加难度，组委会计划移走最多 M 块位于起点与终点之间的岩石（不能移走起点和终点），以使得比赛过程中所有跳跃的最短距离尽可能大。求在最多移走 M 块岩石的条件下，能够得到的最短跳跃距离的最大值。

输入格式

• 第一行包含三个整数 L, N, M，分别表示起点到终点的距离、起点和终点之间的岩石数以及最多可以移走的岩石数。保证 L ≥ 1 且 N ≥ M ≥ 0。
• 接下来 N 行，每行一个整数 D_i（0 < D_i < L），表示第 i 块岩石与起点的距离。岩石按与起点距离从小到大给出，且位置互不相同。

输出格式

• 输出一个整数，表示在移除至多 M 块岩石后，所有跳跃中的最短距离能够达到的最大值。

输入样例 #1

25 5 2
2
11
14
17
21

输出样例 #1

4

题目说明

样例说明：将距离为 2 和 14 的两块岩石移走后，路径上的相邻跳跃距离最小可达 4（例如，从 17 跳到 21，或从 21 跳到终点 25，最短跳跃为 4）。

约束提示：

• 对于 20% 的数据，0 ≤ M ≤ N ≤ 10。
• 对于 50% 的数据，0 ≤ M ≤ N ≤ 100。
• 对于 100% 的数据，0 ≤ M ≤ N ≤ 50,000，1 ≤ L ≤ 1,000,000,000。