问题描述

小可和小美一起玩一个使用带有数字的卡片和硬币的游戏，游戏规则如下：

开始时，小可手里有一张写着 $T$ 的卡片和 $K$ 枚硬币，而小美手里有 $N$ 张卡片。
这个游戏分为 $N$ 轮，每轮小美都要按以下步骤进行。

• 小美选择一张她还没有给小可看过的卡片，并将其展示给小可。设这张卡片上的数字为 $A$。
• 如果小可手里的卡片上的数字为 $B$，那么小可会受到 $|A-B|$ 点伤害。
• 当小可有硬币时，他可以选择给小美一枚硬币，然后用 $A$ 的卡片替换掉 $B$ 的卡片，或者不给小美硬币什么都不做。

在这个游戏中，小可希望最小化每轮受到的最大伤害值。

因此，小可想要探知小美的策略，并且小美无论小可采取什么行动，小美坚信她在第 $i$ 轮出的卡片上的数字是 $A_i$。

请你求出小可在每轮受到的最大伤害值中的最小值。

输入

输入以以下格式从标准输入中给出。

$N$ $T$ $K$ $A_1$ $A_2$ $...$ $A_N$

• 第一行包含三个整数 $N(1≦N≦100,000)$、$T(1≦T≦10^{9})$ 和 $K(1≦K≦N)$，分别表示轮数、小可初始手牌上的数字和硬币的数量。
• 第二行包含 $N$ 个整数，第 $i$ 个整数 $A_i$ $(1≦A_{i}≦10^{9})$ 表示小美在第 $i$ 轮出的卡片上的数字。

评分

本问题有部分测试点。如果能正确处理额外约束条件 $N=K$，将获得 20 分。

输出

输出小可在每轮受到的最大伤害值中的最小值，每个输出占一行，末尾包含换行符。

示例输入1

5 1 1
1 2 3 4 5

示例输出1

2

示例输入2

8 9 3
11 4 5 14 19 19 8 10

示例输出2

6