P14774 [ICPC 2024 Seoul R] Street Development

**ICPC** 街道目前是一个未开发区域，一项大规模开发计划即将启动。在开始开发之前，将使用 $n$ 个遥控机器人收集沿街 $n$ 个重要点的信息，每个机器人负责从一个重要点收集信息。现在的目标是将所有收集到的信息合并到单个机器人中，以找到最高效的开发方案。为了合并信息，机器人可以向左或向右移动，并与携带其他机器人信息的机器人合并信息。此外，每个机器人由其自身的电池供电，所有机器人都配备相同的电池。具体来说，令 $p_1, p_2, \dots, p_n$ 表示机器人收集信息的重要点的位置，按从左到右的顺序排列。要求如下： 1. **ICPC** 街道被视为一个一维区间 $[0, L]$，其中 $L$ 为正整数。重要点 $p_1, p_2, \dots, p_n$ 始终表示为该区间上的整数，包括区间的两个端点。即 $p_1 = 0$ 且 $p_n = L$。初始时，每个机器人位于其中一个重要点上，因此在开始移动前它已拥有该重要点的信息。注意，初始时每个重要点上恰好有一个机器人，这意味着 $n$ 同时也是机器人的数量，且 $n$ 至少为 $2$，至多为 $L+1$。 2. 为了合并来自其他机器人的信息，机器人可以自由地向左或向右移动，每移动 $1$ 单位距离消耗 $1$ 单位电池电量，与方向无关。所有机器人都配备相同的电池容量，其整数值为 $P$，且只在整数距离单位上移动。 3. 当两个或更多机器人在街道上的整数位置相遇时，它们可以合并彼此的信息。例如，如果一个拥有 $p_1$ 和 $p_2$ 信息的机器人与一个拥有 $p_3$ 和 $p_4$ 信息的机器人相遇，则两个机器人随后都将拥有 $p_1, p_2, p_3, p_4$ 这些位置的信息。 4. 机器人仅在移动时消耗电池电量。因此，它们在改变方向或合并其他机器人信息时不消耗电量。 5. 在所有移动结束后，至少有一个机器人必须拥有所有位置 $p_1, p_2, \dots, p_n$ 的信息。 :::align{center}  ::: 例如，上图展示了一个 $L=10$，$n=4$ 的例子，机器人 1、2、3、4（图中 R1、R2、R3、R4）分别收集信息（且初始位于）$p_1=0$，$p_2=3$，$p_3=7$，$p_4=10$。那么，在电池容量 $P=3$ 的情况下，可以执行以下步骤序列： 1. 机器人 1 移动到 $p_2$，机器人 1 和 2 合并彼此的信息。 2. 机器人 4 移动到 $p_3$，机器人 3 和 4 合并彼此的信息。 3. 机器人 2 向右移动 $2$ 单位，机器人 3 向左移动 $2$ 单位，它们在街道上的位置 $5$ 处合并彼此的信息。 完成此过程后，机器人 2 和 3 将拥有所有位置 $p_1, p_2, p_3, p_4$ 的信息。 由于电池比机器人的其他部件昂贵得多，因此确定每个机器人进行高效数据收集所需的最小电池容量非常重要。给定 $L$、$n$ 以及重要点的位置 $p_1, p_2, \dots, p_n$，请编写一个程序计算至少一个机器人拥有所有重要点信息所需的最小电池容量 $P$。

你的程序需要从标准输入读取数据。输入的第一行包含两个正整数 $L$ 和 $n$ ($1 \leq L \leq 10^6$, $2 \leq n \leq L+1$)，其中 $n$ 是街道上机器人（即重要点）的数量，$L$ 是街道右端点的位置。接下来的一行按递增顺序给出 $n$ 个介于 $0$ 和 $L$ 之间且互不相同的整数，表示街道重要点（机器人的初始位置）的位置，其中第一个整数为 $0$，最后一个整数为 $L$。

你的程序需要向标准输出写入结果。输出恰好一行。该行应包含一个整数，表示至少一个机器人拥有所有重要点信息所需的最小电池容量 $P$。

翻译由 DeepSeek V3 完成