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.

题目描述

舔狗 $piero$ 倾慕 $rv$ 已久，但 $rv$ 只想和她在提瓦特的老婆们贴贴。

气急败坏的 $piero$ 穿进提瓦特大陆，把 $rv$ 和她的老婆们抓去庆云顶，庆云顶上有一条笔直的浮空石构成的小道（假设无限长）。 $piero$ 把 $rv$ 的老婆们安置在浮空石上的不同位置。

$rv$ 想确认每个老婆的安危，所以她将从起点（浮空石上第一个老婆的位置）出发，跳跃贴向相邻的老婆（相邻两个老婆之间只能跳跃一步），直至到达终点（浮空石上最后一个老婆的位置）。

然而， $rv$ 与老婆们的贴贴并不总是那么顺利，嫉妒的 $piero$ 会偷走 $rv$ 的一些老婆，使 $rv$ 在比赛过程中的最短跳跃距离尽可能长。由于能力限制， $piero$ 至多从起点和终点之间偷走 $M$ 个老婆（不能偷走起点和终点的老婆）。

$rv$ 只想每一步都有老婆贴，在每一次跳跃后，贴不到老婆的 $rv$ 会悲痛欲绝，从浮空石上失足翻下去。舔狗 $piero$ 会在悬崖下等着英雄救美。

懒狗 $rv$ 不想让舔狗 $piero$ 的计谋得逞，所以她向你求助。

输入格式

输入的第一行包含三个整数 $L，N，M$，分别表示起点老婆到终点老婆的距离，起点和终点之间的老婆数，以及 $piero$ 最多偷走的老婆数。 接下来 $N$ 行，每行一个整数，第 i 行的整数 $D_i$$（0 < D_i < L）$表示第 $i$个老婆与起点老婆的距离。这些老婆按与起点距离从小到大的顺序给出，且不会有两个老婆出现在同一个位置。

输出格式

输出只包含一个整数，即最短跳跃距离的最大值。

样例

25 5 2
2
11
14
17
21

4

说明

$piero$ 将与起点老婆距离为 2 和14 的两个老婆偷走后，最短的跳跃距离为 4（从与起点老婆距离17的老婆贴到距离 21的老婆，或者从距离 21 的老婆贴到终点的老婆）。

数据范围

$0 ≤ M ≤ 50,000，$

$0 ≤ N ≤ 50,000$，

$1 ≤ L ≤ 1,000,000,000$