You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $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 号向右，2 号向左，3 号向左。 50 秒后，2 号传火给 1 号。随后，1 号和 3 号继续移动。** **又过了 25 秒，1 号传火给 3号。

样例2输入

3 2 10
0
200
300

样例2输出

8

开始时，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$ 单调不减。