问题 C: 独木桥（bridge）

问题 C: 独木桥（bridge）

时间限制: 1 Sec  内存限制: 256 MB
提交: 21  解决: 16
[提交][状态][讨论版][命题人:]

题目描述

长度为L米的独木桥上有 n个人，他们每个人都想以最快的时间离开危险的独木桥。 已知每个人在独木桥上的行走速度为 1 米/秒 ，每个人只要能走到独木桥的两个端点中的其 中一个就可以离开独木桥。 由于独木桥的桥面宽度很窄，只能容纳一个人通过，当两个人相遇时，他们无法交错通 过，只能各自调转方向，继续沿反方向行走。 给你独木桥上的人数 n，独木桥的长度L ， 第 i个人的初始位置到独木桥左端点的距离ai米（每个人开始的朝向未知，但他们可以根据需要随时调转行走的方向）。 请计算出所有人同时出发，全部都离开独木桥所需的最短时间

输入

第一行一个整数 n ，表示人数。

第二行一个整数 L，表示独木桥的长度（米）。

第三行是a1 , a2 . . . an ，其中 ai 表示第i个人初始位置到独木桥左端点的距离

输出

输出一行一个整数，表示所有人都离开独木桥所需的最短时间。

样例输入

样例1
3
10
2 6 7
样例2
7
214
11 12 7 13 176 23 191

样例输出

样例1
4
样例2
38

提示


对于50%的数据：1≤n≤10^3



对于100%的数据：1≤n≤10^6,1≤L≤ 10^6，0≤ai<=L

[提交][状态]