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

题目描述

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

工程预算有限，只能拆除 $M$ 个桥墩。请问拆除后最窄地方的最大可能值是多少？

输入格式

第一行输入三个整数 $L,N,M$，分别表示左岸到右岸的距离、桥墩数和可以拆除的桥墩数。

接下来 $N$ 行，每行输入一个整数 $D_i$，表示第 $i$ 个桥墩与左岸的距离。桥墩按与左岸距离从小到大的顺序给出。

输出格式

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

样例

24 4 2
2
11
17
21

6

样例解释

初始间距（包括两岸）为：左岸到桥墩 $1$（$2$）、桥墩 $1$ 到桥墩 $2$（$9$）、桥墩 $2$ 到桥墩 $3$（$6$）、桥墩 $3$ 到桥墩 $4$（$4$）、桥墩 $4$ 到右岸（$3$）。最窄处为 $2$。拆除 $2$ 个桥墩后，可以保留桥墩 $2$（$11$）和桥墩 $3$（$17$），间距变为：左岸到桥墩 $2$（$11$）、桥墩 $2$ 到桥墩 $3$（$6$）、桥墩 $3$ 到右岸（$7$），最窄处为 $6$。不存在让最小间隔大于 $6$ 的方案。

数据范围与提示

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