BN202603 星际救援信标

题目描述

在一条长度为 L 的直线上，道路两端的位置 0 和 L 各有一座救援塔。道路上有 N 个信标，第 i 个信标位于位置 p_i。

每座救援塔发出的信号覆盖半径相同，均为 R。如果某个信标到左侧救援塔或右侧救援塔的距离不超过 R，就认为该信标被覆盖。

请你计算：使所有信标都至少被一座救援塔覆盖时，覆盖半径 R 的最小值是多少。

输入格式

第一行包含两个正整数 L 和 N，分别表示道路长度和信标数量。

第二行包含 N 个正整数 p_1, p_2, ..., p_N，表示各个信标的位置，满足：

0 < p_1 < p_2 < ... < p_N < L

输出格式

输出一个整数，表示覆盖所有信标所需的最小覆盖半径。

样例输入

20 3
3 7 16

样例输出

7

样例说明

当覆盖半径为 7 时：

• 位置 3 的信标距离左侧救援塔为 3；
• 位置 7 的信标距离左侧救援塔为 7；
• 位置 16 的信标距离右侧救援塔为 4。

所有信标都能被至少一座救援塔覆盖。

数据范围

• 1 ≤ L ≤ 10^9
• 1 ≤ N ≤ 10^5
• 0 < p_i < L
• p_i < p_{i+1}