题目描述

每年奶牛们都会举办一场独特的跳格子活动，地点在一条长长的笔直河流上，起点和终点各有一块石头，相距$L$单位（$1 \leq L \leq 10^9$）。在起点和终点之间，还有$N$块石头（$0 \leq N \leq 50000$），每块石头到起点的距离为整数$D_i$（$0 < D_i < L$）。

游戏中，每头奶牛依次从起点石头出发，尝试跳到终点石头，且只能在石头之间跳跃。当然，不够敏捷的奶牛可能因石头间距太小而落水。

Farmer John 为自己的奶牛感到骄傲，但年复一年，他厌倦了观看其他农场的胆小奶牛在间距过近的石头间蹒跚跳跃。他计划移除若干石头，以增加奶牛到达终点所需跳跃的最小距离。已知不能移除起点和终点的石头，且最多可移除$M$块（$0 \leq M \leq N$）。

在开始移石头之前，John 想知道能达到的最大最小跳跃距离。请帮他确定移除最优石头集合后，奶牛必须跳跃的最小距离的最大值。

输入格式

• 第1行：三个空格分隔的整数$L$、$N$和$M$。
• 第2到$N+1$行：每行一个整数，表示某块石头到起点的距离，无重复位置。

输出格式

• 第1行：一个整数，表示移除$M$块石头后，奶牛必须跳跃的最小距离的最大值。

输入样例 1

25 5 2
2
14
11
21
17

输出样例 1

4

样例解释

移除石头前，最小跳跃距离是从起点（0）到2的2单位。移除位置2和14的石头后，剩余石头位置为0、11、17、21、25，此时最小跳跃距离为4（17到21或21到25）。

来源

USACO 2006 十二月银牌赛