← 返回题目列表

AtCoder · arc152_b

B. 传递路径

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

分数: 500 点

问题陈述

有一条很长的又窄又直的路 L 从东向西延伸。两个旅行者将访问这条路。 路边有 N 休息区。从道路西端到道路的距离 i第一个休息区是 a_i (道路两端均无休息区)。 道路很窄,除了休息区外,两个旅行者不能互相擦肩而过或并肩行走。

两名旅行者将沿着如下道路旅行。

  • 时间 0,每位旅客从自己选择的休息区出发(两人可以在同一个休息区出发)。 然后,各自走完路的两端,返回自己的起始休息区。

旅途中,他们可以以最多 的速度沿着道路行走 1,或在休息区休息。 只要他们只在休息区经过,就总是允许改变方向。 两名旅行者到达道路两端并返回起始休息区所需的最少秒数是多少? 可以证明,在本问题的约束条件下,答案始终为整数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq 10^9
  • 0 < a_1 < a_2 < \ldots < a_N < L
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N L
a_1 a_2 \ldots a_N

输出

将答案打印为整数。


示例输入 1

2 6
2 5

示例输出 1

14

让我们将旅行者命名为 A 和 B。另外,请致电 i第休息区简单休息区 i。 这是一次可能的旅行。

一开始,A从休息区出发 1 向东步行,B从休息区出发 2 向东行走,速度均为 1,计划先游东端,再游西端。 然后,两秒后,B回到休息区 2 参观东端后,但 A 仍在休息区之间 1 和 2。 如果B在此休息一秒,A也会到达休息区 2,他们可以互相超越。

之后,如果他们继续以 1 和A在休息区休息 1 两秒,B此时回到起始休息区 13,A 会在某个时间回来 14,完成行程。

这次旅行结果是最佳的:答案是 14.


示例输入 2

2 3
1 2

示例输出 2

6

在这种情况下,最佳行程将允许两个旅行者继续以以下速度行走 1 没有休息。