33OJ
登录 注册

#P17549. [JAG 2026 Summer Camp #2] Warp

[JAG 2026 Summer Camp #2] Warp

题目描述

有一个周长为 LL 的圆,其中 LL 为偶数。圆上的位置沿逆时针方向计量,用范围在 [0,L)[0,L) 内的实数表示。

圆上有 NN 个点,第 ii 个点位于 AiA_i。这些点的位置不一定互不相同。

开始时,你可以任选圆上的一个位置作为起点。

之后,你可以以每秒 11 单位的速度沿圆顺时针或逆时针移动。你可以随时改变移动方向,且改变方向不消耗时间。

此外,你可以随时使用魔法传送,次数不限。魔法传送不消耗时间,会把你移动到圆上与当前位置正对的位置。更精确地说,如果你位于 xx(0≤x<L0\le x<L),一次传送耗时 00 秒,传送后的位置为

$$\begin{cases} x+L/2 & (0\le x<L/2),\\ x-L/2 & (L/2\le x<L). \end{cases}$$

只要你的位置与某个点的位置重合,就视为访问了该点。求将全部 NN 个点都访问至少一次所需的最少时间,单位为秒。

输入格式

输入仅包含一组测试数据,格式如下。

N L
A_1 A_2 ... A_N

整数 NN 表示圆上的点数(1≤N≤2×1051\le N\le 2\times 10^5)。偶数 LL 表示圆的周长(2≤L≤1092\le L\le 10^9)。每个整数 AiA_i 满足 0≤Ai<L0\le A_i<L,表示圆上第 ii 个点的位置(i=1,2,…,Ni=1,2,\ldots,N)。

输出格式

输出访问全部 NN 个点所需的最少时间。可以证明答案为整数。

4 10
0 2 8 9
3
1 10
9
0
7 100
39 57 57 1 99 70 37
33

提示

在样例输入 1 中,可以按以下方式在 33 秒内访问全部 44 个点。

  • 首先,从位置 22 出发,访问第 22 个点。
  • 移动到位置 33,耗时 11 秒。
  • 使用魔法传送到位置 88,耗时 00 秒,同时访问第 33 个点。
  • 移动到位置 99,耗时 11 秒,同时访问第 44 个点。
  • 移动到位置 00,耗时 11 秒,同时访问第 11 个点。