题目描述

每逢过年，奶牛们玩跳石头游戏，这个游戏在一条笔直的河上进行。河上两个石头被作为起点和终点，它们之间的距离为 L ( 1 <= L <= $10^9$ )，还有 N ( 0 <= N <= 50000 )个石头放置在这两个石头之间，每个石头距离起点都有一个独一无二的整数距离 D ( D 小于 L )。

游戏进行的时候，奶牛们从起点开始，依次跳到每一个相邻的石头上，最终到达终点。约翰对自己的奶牛很有信心。他每年都到场观看这些奶牛们的游戏。今年，约翰终于不耐这个游戏的无聊，打算做一些手脚，好让别的农夫的奶牛出丑。他打算除掉 M ( 0 <= M <= N )个石头，使任意两个石头间的最短距离变得尽量大。这样，别人家的奶牛就很有可能失蹄了。

请计算，采取最佳方案移除石头之后，最短距离是多少。注意，约翰不能移除起点和终点的石头。

输入格式

第 1 行输入 L，N，M ;

接下来 N 行，每行一个整数表示一个石头的位置。

输出格式

移除石头后的最短距离。

样例

25 5 2
2
14
11
21
17

4

样例解释

移除之前，最短距离在位置 2 的石头和起点之间；移除位置 2 和位置 14 两个石头后，最短距离变成 17 和 21 或 21 和 25 之间的 4 。