← 返回题目列表

AtCoder · codefestival_2015_qualA_d

D. 坏掉的火车

中文机器翻译题面 查看原题

問題文

在高桥铁道,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 分钟内完成。 有

figure1

入力例2

66 10
8
9
16
23
37
47
51
52
53
64

出力例2

8