AIO 2025 第 3 题：离开跑道

英文题名：Off the Track

题目描述

你的学校有一条长 (L) 米的跑道，(N) 名学生分别站在跑道上的不同位置。

第 (i) 名学生距离跑道起点 (P_i) 米，其中 (P_i) 是 (1) 到 (L-1) 之间的整数，包含两个端点。

你正在和这些学生玩一个游戏。每秒钟，你会喊出以下两种指令中的一种：

• 如果你喊“向前”，所有学生都向跑道终点方向移动 (1) 米。具体来说，位于位置 (p) 的学生会移动到位置 (p+1)。
• 如果你喊“向后”，所有学生都向跑道起点方向移动 (1) 米。具体来说，位于位置 (p) 的学生会移动到位置 (p-1)。

如果一名学生到达跑道起点（位置 (0)）或跑道终点（位置 (L)），那么他就会离开跑道，并停止参与游戏。

当全部 (N) 名学生都离开跑道时，游戏结束。题面末尾给出了两个游戏示例。

如果你可以有策略地决定何时喊“向前”和“向后”，结束游戏最少需要多少秒？

子任务与数据范围

所有测试数据均满足：

• (2\le N\le 200,000)
• (N<L\le 10,000,000)
• 对所有 (i)，(1\le P_i\le L-1)
• 对所有 (1\le i<N)，(P_i<P_{i+1})

最后一个条件表示所有学生的初始位置互不相同，并且按照升序给出。

输入格式

• 第一行包含两个整数 (N) 和 (L)。
• 第二行包含 (N) 个整数，表示学生的初始位置，其中第 (i) 个整数为 (P_i)。

输出格式

输出一个整数，表示结束游戏所需的最少秒数。

样例 1

输入：
2 5
1 3

输出：
3

样例 2

输入：
2 7
2 6

输出：
4

样例 3

输入：
4 15
1 3 11 14

输出：
10

样例解释

• 在样例 1 中，(N=2) 名学生分别位于长 (L=5) 米跑道的位置 (1) 和 (3)。连续喊 (3) 次“向后”，可以在 (3) 秒内结束游戏。不可能在少于 (3) 秒的时间内结束游戏，因此答案为 (3)。

• 在样例 2 中，(N=2) 名学生分别位于长 (L=7) 米跑道的位置 (2) 和 (6)。先喊 (1) 次“向前”，再喊 (3) 次“向后”，可以在 (4) 秒内结束游戏。不可能在少于 (4) 秒的时间内结束游戏，因此答案为 (4)。

• 在样例 3 中，(N=4) 名学生分别位于长 (L=15) 米跑道的位置 (1)、(3)、(11) 和 (14)。先喊 (3) 次“向后”，再喊 (7) 次“向前”，可以在 (10) 秒内结束游戏。

原题图示

图 1：样例输入 1 和样例输入 2 的一种解决过程。图示应从上到下阅读。

图中标签对照：

• Sample Input 1/2：样例输入 1/2
• Yell "Forwards"：喊“向前”
• Yell "Backwards"：喊“向后”