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（整数），原有 N 个基站的位置（距起点整数距离，且已按递增顺序给出），最多可增设 K 个基站。新基站也必须设在整数距离处。铁轨的起点和终点已经设有基站。

目标是：在增设不超过 K 个基站后，使得相邻基站的最大间隔最小，并输出这个最小值。

格式

输入

第 1 行包括三个数 L,N,K，分别表示铁轨的长度，原有基站的数量，以及最多可增设的基站数量。

第 2 行包括递增排列的 N 个整数，分别表示原有的 N 个基站的位置。基站的位置用距起点的距离表示，且一定位于区间 [0,L] 内。

输出

输出 1 行，包含一个整数，表示增设基站后的最大间隔数。

样例

101 2 1
0 101

51

说明/提示

铁轨原来只在起点和终点处有两个信号基站，现在允许新增一个基站，应该把新基站设在距起点 50 或 51 个单位距离处，这样能达到最小的间隔距离 51。

限制

1s, 1024KiB for each test case.