Problem Description

题目描述

在一维部署的日志链路上，操作系统需要把相邻两个活跃节点之间的间隔尽量拉大，以降低同步广播的碰撞概率。

某分布式系统沿一条直线部署了一条日志链路，链路两端各有一个固定节点：左端点在坐标 $0$，右端点在坐标 $L$（这两个端点是固定的，不允许下线）。两端点之间有 $N$ 个中继节点，第 $i$ 个中继节点的坐标为 $D_i$，且 $0 < D_i < L$。链路建成时，相邻节点之间的坐标差称为这段链路的跳距；整条链路的质量由最小跳距衡量。

由于预算限制，运维团队最多可以让 $M$ 个中继节点下线（两个端点节点不能下线）。一个节点下线后，它两侧的节点就不再相邻。小伟希望下线若干（至多 $M$ 个）中继节点之后，使链路的最小跳距尽可能大。

请你求出：在至多让 $M$ 个中继节点下线的前提下，链路最小跳距的最大值。

输入格式

从文件 stone.in 读入。

第一行包含三个整数 $L, N, M$，分别表示链路两端点的距离、两端点之间的中继节点数，以及至多可以下线的中继节点数。保证 $L \ge 1$ 且 $N \ge M \ge 0$。

接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i$（$0 < D_i < L$）表示第 $i$ 个中继节点与左端点的距离。这些坐标按与左端点距离严格递增的顺序给出，且不会有两个节点出现在同一坐标。

输出格式

输出到文件 stone.out。

输出仅一行，包含一个整数，即最小跳距的最大值。

输入输出与文件要求

本题为文件输入输出（IO 赛制），必须使用 freopen 重定向。

freopen("stone.in", "r", stdin);    // 文件输入
freopen("stone.out", "w", stdout);  // 文件输出

样例

样例 1

输入

25 5 2
2
11
14
17
21

输出

4

提示

样例 1 说明

坐标 $2$ 与坐标 $14$ 的两个中继节点下线后，剩下的节点坐标为 $0, 11, 17, 21, 25$，四段跳距分别为 $11, 6, 4, 4$，最小跳距为 $4$。可以证明无法让最小跳距达到 $5$。

关键提示

二分答案：判定"最小跳距能否达到 $x$"时，从左到右贪心即可——若当前点到上一个保留点的距离小于 $x$，就下线当前点（计数 +1），否则保留它。若需要下线的点数不超过 $M$，则 $x$ 可行。

评测方式

本题使用文件输入输出：评测时会把测试数据放到程序运行目录下的 stone.in， 并读取程序生成的 stone.out。请确认你的程序在没有任何标准输入的情况下也能正确运行。

数据规模与约定

• 对于 $20\%$ 的数据，$0 \le M \le N \le 10$；
• 对于 $50\%$ 的数据，$0 \le M \le N \le 100$；
• 对于 $100\%$ 的数据，$0 \le M \le N \le 50000$，$1 \le L \le 10^9$。