题目描述

题目译自 JOISC 2017 Day1 T3「手持ち花火（Sparklers）」

有 $N$ 人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧 $T$ 秒。每个烟花只能被点燃一次。 $1$ 号站在原点，$i$ 号 $(1\le i\le N)$ 到 $1$ 号的距离为 $X_i$。保证 $X_1=0,$ $X_1, X_2, \dots, X_N$ 单调递增（可能有人位置重叠）。 开始时， $K$ 号的烟花刚开始燃烧,，其他人的烟花均未点燃。他们的点火工具坏了，只能用燃着的烟花将未点燃的烟花点燃。当两人位置重叠且其中一人手中的烟花燃着时，另一人手中的烟花就可以被点燃。忽略点火所需时间。 求至少需要以多快的速度跑，才能点燃所有人的烟花（此时可能有些人的烟花已经熄灭了）。速度必须是一个非负整数。

输入格式

第一行有三个整数 $N,K,T$，用空格分隔。 在接下来的 $N$ 行中，第 $i$ 行 $(1\le i\le N)$ 有一个整数 $X_i$。

输出格式

一个整数，表示要想点燃所有人的烟花，全程中最大速度的最小值。

样例

样例输入 1

3 2 50
0
200
300

样例输出 1

2

样例解释 1

开始时，$1$ 号向右，$2$ 号向左，$3$ 号向左。 $50$ 秒后，$2$ 号传火给 $1$ 号 我真的不是黑魂玩家。随后，$1$ 号和 $3$ 号继续移动。 又过了 $25$ 秒，$1$ 号传火给 $3$ 号。

样例输入 2

3 2 10
0
200
300

样例输出 2

8

样例解释 2

开始时，$1$ 号向右，$2$ 号向右，$3$ 号向左。 $3$ 秒后，$2$ 号停止移动。 又过了 $6.5$ 秒，$3$ 号到达 $2$ 号所在位置，$3$ 号停止移动。 又过了 $0.5$ 秒，$2$ 号传火给 $3$ 号。 又过了 $9$ 秒，$3$ 号传火给 $1$ 号。

样例输入 3

20 6 1
0
2
13
27
35
46
63
74
80
88
100
101
109
110
119
138
139
154
172
192

样例输出 3

6

限制与提示

对于 $30\%$ 的数据，$N \le 20$。 对于 $50\%$ 的数据，$N \le 1000$。 对于 $100\%$ 的数据，$1\le K, N \le 10^5, 1\le T\le 10^9, 0\le X_i\le 10^9 (1\le i\le N), X_1 = 0, \{X_N\}$ 单调递增。