問題文
在高桥铁道,N 两列火车的一部分坏了,所以M 机械师将对其进行检查。
i 第二个机械师开始,X_i 我在两辆车里。每个机械师都可以检查他们当前所在的车辆并移动到下一辆车。检查一辆车并不需要太多时间,但移动到下一辆车需要 需要 1 分钟。
所有车辆至少 1 当另一位机械师检查完该项目后,检查工作结束。巡检工作多少分钟可以完成?
入力
输入是按以下格式从标准输入给出的。
N M X_1 X_2 : X_M
- 1 行中,2 整数 给出了 N (1 ≦ N ≦ 10^9), M (1 ≦ M ≦ 10^5, M ≦ N) 用空格分隔。这是因为火车 N 由两辆车组成,机械师 M 表示有人。 来自行
- 2 从线 M 行提供有关机械师的信息。其中 i (1 ≦ i ≦ M) 行包含一个整数 给出了 X_i (1 ≦ X_i ≦ N) 。这是i 第一位机械师开始 X_i 表示您同时乘坐两辆车。然而,X_i 保证全部不同。此外,机械信息是 1 按照与两辆车的接近程度的顺序给出,即 X_j < X_{j+1} (1 ≦ j ≦ M-1) 有保证。 如果正确答案是满足
部分点
针对此问题设置了部分分数。 如果正确答案是满足
- N ≦ 100 的数据集, 除了上述之外,如果正确答案是满足20 点。
- N ≦ 500,000 的数据集, 60 点。
- 除了上述内容之外,如果答案对于没有附加约束的数据集是正确的, 20 点。
出力
检查工作所需的最短时间(以分钟为单位)。 在 1 行输出。在输出末尾插入换行符。
入力例1
17 5 1 5 10 15 16
出力例1
3
如果机械师如下图所示移动, 3 分钟内完成。 有
入力例2
66 10 8 9 16 23 37 47 51 52 53 64
出力例2
8