题目描述

河的左岸到右岸之间有一座年久失修、已经废弃的大桥，有 $N$ 个桥墩影响船只通行。现在要拆除部分桥墩，使得通航能力最大。通航能力由最窄的地方决定，这个地方可能是岸与桥墩之间，也可能是桥墩之间。工程预算有限，只能拆除 $M$ 个桥墩。如何安排工程，才能使得通航能力尽可能的大？

输入格式

第一行包含三个整数 $L, N, M$，分别表示左岸到右岸的距离、桥墩数和可以拆除的桥墩数。 接下来 $N$ 行，每行一个整数 $D_i$，表示第 $i$ 个桥墩与左岸的距离。桥墩按与左岸距离从小到大的顺序给出。

输出格式

一个整数，表示拆除了 $M$ 个桥墩之后，最窄地方的最大值。

样例

24 4 2
2
11
17
21

6

提示

岸与桥墩的距离序列（包括左岸 $0$ 和右岸 $24$）为：$0, 2, 11, 17, 21, 24$。拆除 $2$ 个桥墩后（例如拆除 $11$ 和 $17$），间距变为 $2-0=2$，$21-2=19$，$24-21=3$，最窄处为 $2$；若拆除 $2$ 和 $11$，间距为 $11-0=11$（但 $2$ 被拆，实际是 $17-0=17$）需要重新计算：保留 $17,21$，间距为 $17-0=17$，$21-17=4$，$24-21=3$，最窄 $3$；最优解为保留 $2,17,21$（拆除 $11$？但需拆两个），样例输出 $6$，可能保留 $2$ 和 $11$，拆除 $17,21$，间距为 $2-0=2$，$11-2=9$，$24-11=13$，最窄 $2$；保留 $11,17$，拆除 $2,21$，间距 $11-0=11$，$17-11=6$，$24-17=7$，最窄 $6$。故答案为 $6$。

数据范围

• $0 \le M \le N \le 50000$
• $1 \le L \le 10^9$
• $0 < D_i < L$，且 $D_i$ 严格递增