题目描述

提醒：每个子任务都是捆绑测试，只有该子任务内所有测试点正确的时候你才能得到这个子任务的所有分数。

安东诺夫邀请了他的 $m$ 个朋友来到他的花园里面玩。在他的花园里面画了一行从左到右总共 $n+1$ 个格子，编号从 $0\sim n$。

一开始他的朋友们每个人都在一个格子上，第 $i$ 个人在第 $a_i$ 个格子上。

每秒钟他的朋友都可以决定做以下两件事的其中一件：

1. 向左跳一格。
2. 向右跳一格。

安东诺夫想知道他的朋友们至少需要花多少时间才能把所有的格子都访问一遍。

输入格式

第一行两个数 $n,m$。

第二行 $m$ 个整数 $a_1\sim a_m$。

输出格式

最少多少秒才能让所有的格子都访问一遍。

5 1
0

5

5 1
2

7

5 2
0 5

2

10 2
0 8

6

5 2
3 3

3

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 10^9$，$1\le m\le 10^6$，$0\le a_i\le n$。

• 子任务 1（10 分）：保证 $m=1$。
• 子任务 2（20 分）：保证 $m=2$。
• 子任务 3（30 分）：保证 $n=10^3$。
• 子任务 4（40 分）：没有特殊限制。