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

起初，JOI-kun 和他的朋友们分散站在一条东西走向的笔直街道上。JOI-kun 和他的朋友们编号为 $1$ 到 $N$。对于每一对 $i < j$，第 $i$ 个人站在第 $j$ 个人的西侧，或者两人站在同一位置。第 $i$ 个人距离最西端（即第 $1$ 个人）的距离为 $X_i$ 米。JOI-kun 是第 $K$ 个人。

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

因此，他们决定先点燃 JOI-kun 的仙女棒。然后，他们通过将未点燃的仙女棒接触正在燃烧的仙女棒来传递火种。

由于仙女棒只能燃烧 $T$ 秒，JOI-kun 和他的朋友们必须通力合作来传递火种。当他们通过正在燃烧的仙女棒点燃另一根仙女棒时，必须满足以下条件：

• 必须在点燃后 $T$ 秒内将仙女棒接触到正在燃烧的仙女棒。他们可以在恰好 $T$ 秒时进行接触。
• 计划点燃的仙女棒此前必须未被点燃过。
• 持有正在燃烧的仙女棒的人和持有未点燃的仙女棒的人必须处于同一位置。

我们忽略从一根仙女棒向另一根仙女棒传递火种所需的等待时间。

由于 JOI-kun 和他的朋友们起初是分散站立的，他们必须适当地移动以传递火种。他们可以以任意速度向东或向西奔跑。但是，玩耍时跑得太快很危险。因此，他们规定奔跑速度不得超过 $s$ 米/秒，其中 $s$ 是一个非负整数。

他们应该如何设定速度限制，以便将火种传递给所有仙女棒？

题目描述

给定仙女棒燃烧的时间以及 JOI-kun 和他朋友们的初始位置，编写一个程序，计算在速度限制为 $s$ 米/秒的情况下，能够将火种传递给所有仙女棒的最小整数 $s$。

输入格式

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

• 第一行包含三个空格分隔的整数 $N, K, T$。这表示有 $N$ 个人，JOI-kun 是第 $K$ 个人，仙女棒燃烧时间为 $T$ 秒。
• 接下来的 $N$ 行中的第 $i$ 行 ($1 \le i \le N$) 包含一个整数 $X_i$。这表示第 $i$ 个人起初距离最西端的人的距离为 $X_i$ 米。

输出格式

输出一行到标准输出。输出包含能够将火种传递给所有仙女棒的最小整数 $s$。

数据范围

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

• $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 分]：无附加限制。

样例

样例输入 1

3 2 50
0
200
300

样例输出 1

2

样例输入 2

3 2 10
0
200
300

样例输出 2

8

样例输入 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