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$ 也是机器人的数量，且满足 $2 \le n \le 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$ 的信息。

例如，上图展示了一个 $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 \le L \le 10^6, 2 \le n \le L + 1$)，其中 $n$ 是机器人和重要点的数量，$L$ 是街道右端点的位置。接下来的行中，按递增顺序给出 $n$ 个介于 0 到 $L$ 之间的不同整数，表示街道上重要点的位置（机器人的初始位置），其中第一个整数为 0，最后一个为 $L$。

输出格式

程序向标准输出写入数据。仅输出一行，包含一个整数，表示至少有一个机器人获取所有重要点信息所需的最少电池容量 $P$。

样例

样例输入 1

10 4
0 3 7 10

样例输出 1

3

样例输入 2

100 5
0 97 98 99 100

样例输出 2

49

样例输入 3

1 2
0 1

样例输出 3

1