You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

每年奶牛们都会组织一场奇怪的跳石头游戏。它的场地是一条长长的河，第一个石头和最后一个石头的距离为L(1 <= L <= 1,000,000,000)，除了这两个石头之外还有N个石头(0 <= N <= 100,000)，（在这N个石头中）每个石头和第一个石头的距离分别是Di。每头牛轮流从第一个石头开始，尝试到达最后一个石头，当然了，有些牛是到不了的啦。约翰希望在去掉M(0<=M<=N)个石头之后（第一个和最后一个石头不能去掉），使得相邻两个石头的距离的最小值最大。输出这个最大值。

输入格式

第一行三个整数L, N, M
第二行到第N+1行每行一个整数表示某个石头距离开始位置的距离，没有两个石头会在同一个位置。

输出格式

相邻两个石头距离中最小值要最大，输出这个最大值。

样例

25 5 2
2
14
11
21
17

4

提示

起点位置为0