/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ L の細長い一直線の道が東西に伸びており、この道を 2 人の旅人が訪れます。 この道には N 個の休憩所があり、i 番目の休憩所は、道の西端から a_i の地点にあります （ただし、どの休憩所も道の端には存在しません）。 この道はとても細いため、休憩所以外の地点で 2 人がすれ違ったり、横に並んで歩いたりすることはできません。
2 人の旅人は、この道で次のような旅をします。
- 時刻 0 に、それぞれ好きな休憩所を選んで出発点とする（ 2 人が同じ休憩所を選んでもよい）。 その後、それぞれ道の両端を訪れたあと、自身の出発点に戻る。
2 人は、毎秒 1 以下の速さで道を歩くか、休憩所で休憩することができます。 休憩所以外の地点ですれ違わない限り、旅の途中いつでも向きを変えることは可能です。 両者が道の両端を訪れて出発点に戻ってくるまで、最短で何秒かかるでしょうか。 ただし、この問題の制約下では答えが整数になることが証明できます。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq L \leq 10^9
- 0 < a_1 < a_2 < \ldots < a_N < L
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N L a_1 a_2 \ldots a_N
出力
答えを整数で出力せよ。
入力例 1
2 6 2 5
出力例 1
14
2 人の旅人を A、B とします。また、以下では i 番目の休憩所を単に休憩所 i と呼びます。 例えば、2 人は以下のような旅をすることができます。
最初に A が休憩所 1 から東側に、B が休憩所 2 から東側に速さ 1 で歩き始め、両者とも東端→西端の順に訪れることにします。 すると、B は 2 秒後に東端を訪れて休憩所 2 に戻って来ることができますが、A はまだ休憩所 1 と 2 の間です。 ここで B が 1 秒休憩すると、A も休憩所 2 にたどり着き、すれ違いが可能になります。
その後、再び両者が速さ 1 で歩き続け、A が休憩所 1 で 2 秒だけ休憩した場合、 B は出発から 13 秒後、A は 14 秒後に元の休憩所に戻り、旅を終えることができます。
実はこれは最善の方法の 1 つであり、答えは 14 となります。
入力例 2
2 3 1 2
出力例 2
6
この場合は、適切な方法を取ると、両者が休憩することなく速さ 1 で歩き続けることができます。
Score : 500 points
Problem Statement
There is a narrow straight road of length L stretching east to west. Two travelers will visit this road. Along the road, there are N rest areas. The distance from the west end of the road to the i-th rest area is a_i (no rest area is at either end of the road). The road is so narrow that the two travelers cannot pass each other or walk side by side except at the rest areas.
The two travelers will take a trip along the road as follows.
- At time 0, each traveler starts at a rest area of their choice (the two may start at the same rest area). Then, each visits both ends of the road, and returns to their own starting rest area.
During the trip, they can walk along the road at a speed of at most 1, or rest at a rest area. As long as they only pass each other at the rest areas, it is always allowed to change direction. What is the smallest number of seconds needed for both travelers to visit both ends of the road and return to their starting rest areas? It can be proved that the answer is always an integer under the Constraints of this problem.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq L \leq 10^9
- 0 < a_1 < a_2 < \ldots < a_N < L
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N L a_1 a_2 \ldots a_N
Output
Print the answer as an integer.
Sample Input 1
2 6 2 5
Sample Output 1
14
Let us name the travelers A and B. Also, call the i-th rest area simply rest area i. Here is a possible trip.
At the beginning, A starts at rest area 1 walking to the east, and B starts at rest area 2 walking to the east, both at a speed of 1, planning to visit the east end first and then the west end. Then, two seconds later, B is back at rest area 2 after visiting the east end, but A is still halfway between rest areas 1 and 2. If B rests here for one second, A will also arrive at rest area 2, where they can pass each other.
Afterward, if they continue to walk at a speed of 1 and A rests at rest area 1 for two seconds, B will be back at the starting rest area at time 13, and A will be back at time 14, completing the trip.
This trip turns out to be optimal: the answer is 14.
Sample Input 2
2 3 1 2
Sample Output 2
6
In this case, an optimal trip will allow both travelers to keep walking at a speed of 1 without resting.