小S和小M去看花火大会。
一共有 $n$ 个人按顺序排成一排,每个人手上有一个仅能被点燃一次的烟花。最开始时第 $K$ 个人手上的烟花是点燃的。
烟花最多能燃烧 $T$ 时间。每当两个人的位置重叠且其中一个人手上的烟花是点燃的时,另一个人手上的烟花可以被点燃。
现在小M想要知道,每个人至少需要以多快的速度 $s$ 奔跑,才能使得每个人手中的烟花都能被点燃。
可怜的小M当然不会啦,所以她向你求助。
输入格式
第一行三个整数 $n,K,T$。意义如题面所示。
接下来 $n$ 行,每行一个整数 $x_i$,表示第 $i$ 个人的位置。
输出格式
一行一个整数,表示最小的整数 $s$ 使得每个人手中的烟花都能被点燃。
样例一
input
3 2 50 0 200 300
output
2
样例二
input
3 2 10 0 200 300
output
8
样例三
input
20 6 1 0 2 13 27 35 46 63 74 80 88 100 101 109 110 119 138 139 154 172 192
output
6
限制与约定
对于所有数据,
$1\le K\le n\le 10^5,1\le T\le 10^9 ,0\le x_i\le 10^9 ,x_1=0,x_i \le x_j(1\le i\le j \le n)$。
子任务 | 分值 | $n$ |
---|---|---|
1 | 30 | $\le 20$ |
2 | 20 | $\le 1000$ |
3 | 50 | $\le 10^5$ |
时间限制:$2\texttt{s}$
空间限制:$256\texttt{MB}$