题目描述

JOI 君和他的朋友们将玩仙女棒。总共有 $N$ 个人，包括 JOI 君和他的朋友们。如果某人点燃一根仙女棒，它会持续燃烧恰好 $T$ 秒。

一开始，JOI 君和他的朋友们沿着一条从东向西延伸的直线街道分散站立。JOI 君和他的朋友们被编号为 $1$ 到 $N$。对于任意 $i, j$，若 $i < j$，则第 $i$ 个人站在第 $j$ 个人的西侧，或者第 $i$ 个人与第 $j$ 个人站在同一位置。第 $i$ 个人距离最西侧的人（即第 $1$ 个人）的距离为 $X_i$ 米。JOI 君是第 $K$ 个人。

当他们开始玩仙女棒时，他们发现打火机燃料不足，只能点燃一根仙女棒。

因此，他们决定先点燃 JOI 君的仙女棒，然后通过用燃烧的仙女棒接触其他仙女棒来点燃它们。

由于每根仙女棒只能燃烧 $T$ 秒，JOI 君和他的朋友们必须合作，将火势传递给所有仙女棒。当他们从一根燃烧的仙女棒点燃另一根仙女棒时，必须满足以下条件：

• 他们必须在点燃仙女棒后的 $T$ 秒内接触一根燃烧的仙女棒。他们可以在恰好 $T$ 秒后进行接触。
• 他们计划点燃的仙女棒此前不能已被点燃。
• 持有燃烧仙女棒的人与持有未点燃仙女棒的人必须处于同一位置。

我们忽略从一根仙女棒点燃另一根仙女棒所需的等待时间。

由于 JOI 君和他的朋友们一开始是分散站立的，他们必须适当移动以传递火势。他们可以以任意速度向西或向东奔跑。但奔跑过快在玩耍时是危险的。因此，他们将制定规则：他们的速度不得超过每秒 $s$ 米。这里，$s$ 是一个非负整数。

他们应如何设定速度上限，才能将火势传递给所有仙女棒？

任务

给定仙女棒燃烧的持续时间以及 JOI 君和他的朋友们的初始位置，编写一个程序，计算最小的整数 $s$，使得当速度上限为每秒 $s$ 米时，他们能够将火势传递给所有仙女棒。

输入格式

从标准输入读取以下数据：

• 第一行包含三个由空格分隔的整数 $N$、$K$、$T$。表示共有 $N$ 个人，JOI 君是第 $K$ 个人，且一根仙女棒可燃烧 $T$ 秒。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $X_i$。表示第 $i$ 个人在初始时距离最西侧的人为 $X_i$ 米。

输出格式

向标准输出写入一行。该行输出包含最小的整数 $s$，使得当速度上限为每秒 $s$ 米时，他们能够将火势传递给所有仙女棒。

3 2 50
0
200
300

2

3 2 10
0
200
300

8

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

6

提示

样例 1 解释

在本样例输入中，速度上限可以为每秒 $2$ 米。第一个人向东移动，第二个人向西移动，第三个人向西移动；他们的速度均为每秒 $2$ 米。经过 $50$ 秒后，第二个人将火传递给第一个人。随后，第一个人向东移动，第三个人向西移动；他们的速度仍为每秒 $2$ 米。再经过 $25$ 秒后，第一个人将火传递给第三个人。若速度上限为每秒 $1$ 米，则他们无法将火势传递给所有仙女棒。

样例 2 解释

在本样例输入中，速度上限可以为每秒 $8$ 米。第一个人向东移动，第二个人向东移动，第三个人向西移动；他们的速度均为每秒 $8$ 米。经过 $3$ 秒后，第二个人停止移动，而第一和第三个人继续移动。再经过 $6.5$ 秒后，第二和第三个人到达同一位置，但他们并未传递火势；第二和第三个人停止移动，第一个人继续移动。再经过 $0.5$ 秒后，第二个人将火传递给第三个人；第一个人继续移动，第三个人向西移动，速度为每秒 $8$ 米。再经过 $9$ 秒后，第一和第三个人到达同一位置，第三个人将火传递给第一个人。若速度上限为每秒 $7$ 米，则他们无法将火势传递给所有仙女棒。

数据范围

所有输入数据满足以下条件：

• $1 \le K \le N \le 100\,000$。
• $1 \le T \le 1\,000\,000\,000$。
• $0 \le X_i \le 1\,000\,000\,000$（$1 \le i \le N$）。
• $X_1 = 0$。
• $X_i \le X_j$（$1 \le i \le j \le N$）。

子任务

共有 3 个子任务。每个子任务的得分及附加约束如下：

子任务 1 [30 分]

• $N \le 20$。

子任务 2 [20 分]

• $N \le 1\,000$。

子任务 3 [50 分]

无额外约束。

翻译由 Qwen3-235B 完成