题目描述
长度为L米的独木桥上有n个人,他们每个人都想以最快的时间离开危险的独木桥。已知每个人在独木桥上的行走速度为1米/秒,每个人只要能走到独木桥的两个端点中的其中一个就可以离开独木桥。
由于独木桥的桥面宽度很窄,只能容纳一个人通过,当两个人相遇时,他们无法交错通过,只能各自调转方向,继续沿反方向行走。
给你独木桥上的人数n,独木桥的长度L,第i个人的初始位置到独木桥左端点的距离ai米(每个人开始的朝向未知,但他们可以根据需要随时调转行走的方向)。
请计算出所有人同时出发,全部都离开独木桥所需的最短时间。
输入
第一行一个整数n,表示人数。
第二行一个整数L,表示独木桥的长度(米)。
第三行是a1,a2...an,其中 ai表示第i个人初始位置到独木桥左端点的距离。
1 ≤n ≤ 106,1≤L≤106,0≤ai≤L。
输出
输出一行一个整数,表示所有人都离开独木桥所需的最短时间。
提示
样例说明:三个人同时出发,第一个人向左走,需要2秒离开桥,第二个人向右走需要4秒离开桥,第三个人向右走需要3秒离开桥。所以,4秒后,三个人都离开了独木桥。
样例2输入:
7
214
11 12 7 13 176 23 19
输出:
38