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

跳石（rock）

题目描述

一条笔直的河道长度为 $L$，起点位置为 $0$，终点位置为 $L$。河道中间有 $n$ 块石头，第 $i$ 块石头的位置为 $x_i$。

Y 同学需要从起点跳到终点，只能落在起点、终点或没有被移走的石头上。现在最多可以移走 $k$ 块中间的石头。

移走若干石头后，设相邻可落脚位置之间距离的最小值为 $d$。请你最大化这个最小距离 $d$，并输出能够得到的最大值。

输入格式

第一行包含三个整数 $n,k,L$。

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$，表示石头的位置。保证这些位置严格递增。

输出格式

输出一行一个整数，表示相邻可落脚位置最小距离的最大可能值。

样例

样例输入 #1

5 2 25
2 11 14 17 21

样例输出 #1

4

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le n \le 2\times 10^5$，$0 \le k \le n$，$1 \le x_1 < x_2 < \cdots < x_n < L \le 10^9$。

• 特殊性质 A：保证 $k=0$。
• 特殊性质 B：保证 $x_i=i\times t$，且 $L=(n+1)\times t$，其中 $t$ 为正整数。