#ARC152B. 狭路相逢

狭路相逢

狭路相逢

时间限制:2s
空间限制:1024MB

题目描述

有一条长为 LL 的狭窄直路,路上有 NN 个休息站,第 ii 个休息站距西端 aia_i。除休息站外,两名旅人不能相互经过,也不能并排行走。

时刻 00,两人各自任选一个休息站出发,可以选择同一处。每个人都要访问道路两端,再回到自己的出发站。两人可以以不超过每秒 11 的速度行走,也可以在休息站等待,并可随时改变方向;但相互经过只能发生在休息站。求两人都完成旅行所需的最短时间。

输入格式

N L
a_1 a_2 ... a_N

输出格式

输出最短时间。

样例输入 1

2 6
2 5

样例输出 1

14

样例输入 2

2 3
1 2

样例输出 2

6

数据范围

  • 1≤N≤2×1051\le N\le2\times10^5;
  • 1≤L≤1091\le L\le10^9;
  • 0<a1<a2<⋯<aN<L0<a_1<a_2<\cdots<a_N<L。
子任务编号 分值 特殊限制
1 10 N=1N=1
2 20 存在 i,ji,j 使 ai+aj=La_i+a_j=L
3 40 N≤2000N\le2000
4 30 无特殊限制