题目描述

小云在一个非常大的环形迷宫中，迷宫中共有首尾相连的$m$个格子，迷宫出口在其中某一个格子中，小云想要尽快逃离迷宫。小云有$n$个机器人可以帮助他寻找出口，每个机器人在预先设置好的位置$a_i$，小云可以为每个机器人设置一个搜索方向（顺时针、逆时针），每个机器人每个单位时间会沿着该方向前进一格并检查该格子是否有出口，中途不允许调整搜索方向，当所有格子全部被检查一遍后才能保证小云可以逃离迷宫，小云逃离迷宫不需要花费额外时间（机器人初始所在的位置默认在时刻 0 被检查），请帮助小云计算他最少需要多少时间才能逃离迷宫？

输入输出格式

输入格式：

• 输入的第一行包含一个整数$m$($1\leq m \leq 1,000,000,000$)，表示环形迷宫的格子数量；
• 输入的第二行包含一个整数$n$($1\leq n \leq 100,000$)，表示机器人个数；
• 输入的最后一行，包含n个整数$a_1,a_2,…,a_n$ ($1\leq a_i \leq m$)，其中$a_i$表示第$i$个机器人初始所在的位置，输入数据保证没有两个机器人初始在同一个位置(在行走过程中机器人们当然可能会相遇）。

输出格式：

• 输出一行包含一个整数为小云最少需要多少时间能够逃离迷宫（当机器人检查完所有的格子时，小云可以立刻逃离迷宫）。

输入输出样例

输入样例1:

4
2
1 3

输出样例1:

1

样例说明1:

令两个机器人同时朝着一个方向前进，一个单位时间后所有格子均已被检查

输入样例2:

9
3
1 6 8

输出样例2:

3

样例说明2:

第一个机器人向后走 3 个单位时间覆盖 2,3,4，第二个机器人向后走 3 个单位时间覆盖7,8,9，第三个机器人向前走 3 个单位时间覆盖 7,6,5。

输入样例3:

50
3
22 25 46

输出样例3:

23

样例说明3:

第一个机器人向前走 23 个单位时间覆盖 49～21，第二个机器人向后走 23 个单位时间覆盖26～48，第三个机器人向前走 23 个单位时间覆盖 23～45。

测试点

语言|C|C++|Python|JAVA -|-|-|-|- 每个测试点时限|2.0秒|2.0秒|8.0秒|2.0秒 内存限制|512MB|512MB|512MB|512MB 测试点数目|20|20|20|20 测试点是否等分|是|是|是|是