题目背景

EC-Final 的赛程安排极其紧凑，开幕式、热身赛、赞助商宣讲会、教练会议……各种活动把江学长的时间切得稀碎。 众所周知，Jiangrc 学长如果在比赛前一天没有获得足够长的“连续睡眠”，第二天在赛场上就会疯狂把签到题写 WA。 为了保证队伍在 EC-Final 能顺利夺金，Jiangrc 决定大胆地“翘掉”一些无关紧要的赛前活动，以此来最大化他最长的一段连续休息时间。

题目描述

从 EC-Final 报到（时刻 $0$）到正式赛开始（时刻 $L$），总共有 $L$ 分钟。 在这期间，组委会安排了 $N$ 个既定活动，第 $i$ 个活动在时刻 $D_i$ 准时开始并瞬间结束（假设活动本身不消耗时间，只会打断休息）。 Jiangrc 学长最多可以“翘掉” $M$ 个活动（移出他的时间表）。他希望在移除至多 $M$ 个活动后，剩下的活动（包括时刻 $0$ 和时刻 $L$）之间最短的时间间隔尽可能大。 请你帮他算出，这个最短的时间间隔最大能是多少？

输入格式

第一行包含三个整数 $L, N, M$（$1 \le N \le 5 \times 10^4$, $0 \le M \le N$, $1 \le L \le 10^9$），分别表示总时长、活动数量和最多可以翘掉的活动数。 接下来 $N$ 行，每行一个整数 $D_i$（$0 < D_i < L$），表示每个活动的时刻。保证输入的 $D_i$ 是严格单调递增的。

输出格式

输出一个整数，表示移除至多 $M$ 个活动后，最短时间间隔的最大值。

样例

25 5 2
2
11
14
17
21

4

样例解释

Jiangrc 可以翘掉时刻 $2$ 和 $14$ 的两个活动。剩下的关键节点为 $0, 11, 17, 21, 25$。 它们之间的时间间隔分别为 $11, 6, 4, 4$。最短的时间间隔为 $4$。这是所有方案中能得到的最大值。