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

横渡宇宙暗流

题目背景

在探索一个代号为 "JJJ" 的星系时，噜噜和一只羊的飞船遭遇了一片广阔的“宇宙暗流”。这片暗流无法直接飞越，但其中散布着许多稳定的“奇点”小行星，可以作为临时的跳板。

他们必须从暗流的起点（可以看作岸边）出发，通过在这些奇点小行星之间进行短程跃迁，最终到达暗流的终点（对岸）。

然而，他们的跃迁引擎有一个奇特的限制：为了保证航行的趣味性和挑战性，他们希望在移除一部分小行星后，使得必须进行的最短一次跃迁距离尽可能地长。

问题描述

宇宙暗流可以看作一个数轴。起点在坐标 $0$，终点在坐标 $L$。在起点和终点之间，有 $N$ 个奇点小行星，第 $i$ 个小行星的坐标为 $d_i$。

噜噜和一只羊可以从起点、任意一个小行星，跳到另一个坐标更大的小行星或终点。

他们拥有移除星体的能力，最多可以移除 $M$ 个小行星。

请你帮助他们计算，在移除不超过 $M$ 个小行星后，从起点到终点所需要的所有跃迁中，最短的那一次跃迁距离最大可以是多少？

输入格式

第一行包含三个整数 $L, N, M$，分别代表暗流的宽度（终点坐标），奇点小行星的数量，以及最多可以移除的小行星数量。

第二行包含 $N$ 个整数 $d_1, d_2, \dots, d_N$，表示 $N$ 个小行星的坐标。

输出格式

输出一个整数，表示最短跃迁距离的最大值。

样例输入与输出

25 5 2
2 11 14 17 21

4

样例解释

起点在0，终点在25，小行星在 {2, 11, 14, 17, 21}。 所有可作为跳板的点（包含起点和终点）按坐标排序后为 {0, 2, 11, 14, 17, 21, 25}。 相邻点之间的距离为 {2, 9, 3, 3, 4, 4}。当前最短跃迁距离是 2。

我们的目标是移除最多 2 个小行星，使得这个“最短跃迁距离”变大。 一种最优策略是移除坐标为 2 和 14 的小行星。 移除后，剩下的跳板点为 {0, 11, 17, 21, 25}。 相邻点之间的距离变为 {11, 6, 4, 4}。 此时，最短的跃迁距离是 4。可以证明，不存在移除不超过2个小行星的方案，使得最短跃迁距离大于4。

数据规模与约定

• 对于 $100\%$ 的数据，$1 \le L \le 10^9$, $0 \le N \le 50000$, $0 \le M \le N$。
• $0 < d_i < L$，且所有 $d_i$ 互不相同。输入中的 $d_i$ 不保证有序。

子任务划分:

• 子任务 1 (30分): $N \le 20$。
• 子任务 2 (30分): $N \le 2000$。
• 子任务 3 (40分): 无特殊限制。