B - Tree Burning Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

高橋湖の周長は L です。高橋湖の周上には湖の所有者である高橋君の家があります。 高橋湖の周上の地点には高橋君の家から反時計回りに測った距離を用いて、0 以上 L 未満の実数の座標が定まっています。

高橋湖の周上には木が N 本生えています。i 本目の木は座標 X_i に生えています。高橋君の家のある座標 0 には木は生えていません。

高橋君は、自分の家からはじめて、以下の行動を繰り返します。

  • すべての木を燃やし終えている場合、終了する。
  • 時計回りまたは反時計回りの向きを指定する。
  • 初めてまだ燃やしていない木のある座標に到達するまで、指定した方向に高橋湖の周上を歩き続ける。
  • 木のある座標に到達したら、その木を燃やしてその場に立ち止まり、最初に戻る。

この行動を通じて、高橋君が歩く距離の合計の最大値を求めてください。

制約

  • 2 \leq L \leq 10^9
  • 1 \leq N \leq 2\times 10^5
  • 1 \leq X_1 < ... < X_N \leq L-1
  • 入力はすべて整数である

部分点

この問題には部分点が設定されている。

  • N \leq 2000 を満たす入力に正解すると、300 点が得られる。

入力

入力は以下の形式で標準入力から与えられる。

L N
X_1
:
X_N

出力

高橋君が歩く距離の合計の最大値を出力せよ。

入力例 1

10 3
2
7
9

出力例 1

15

以下のような行動で、高橋君は距離 15 を歩きます。

  • 反時計回りに距離 2 ぶんだけ歩き、座標 2 にある木を燃やして立ち止まる。
  • 反時計回りに距離 5 ぶんだけ歩き、座標 7 にある木を燃やして立ち止まる。
  • 時計回りに距離 8 ぶんだけ歩き、座標 9 にある木を燃やして立ち止まる。

入力例 2

10 6
1
2
3
6
7
9

出力例 2

27

入力例 3

314159265 7
21662711
77271666
89022761
156626166
160332356
166902656
298992265

出力例 3

1204124749

Score : 800 points

Problem Statement

Takahashi Lake has a perimeter of L. On the circumference of the lake, there is a residence of the lake's owner, Takahashi. Each point on the circumference of the lake has a coordinate between 0 and L (including 0 but not L), which is the distance from the Takahashi's residence, measured counter-clockwise.

There are N trees around the lake; the coordinate of the i-th tree is X_i. There is no tree at coordinate 0, the location of Takahashi's residence.

Starting at his residence, Takahashi will repeat the following action:

  • If all trees are burnt, terminate the process.
  • Specify a direction: clockwise or counter-clockwise.
  • Walk around the lake in the specified direction, until the coordinate of a tree that is not yet burnt is reached for the first time.
  • When the coordinate with the tree is reached, burn that tree, stay at the position and go back to the first step.

Find the longest possible total distance Takahashi walks during the process.

Partial Score

A partial score can be obtained in this problem:

  • 300 points will be awarded for passing the input satisfying N \leq 2000.

Constraints

  • 2 \leq L \leq 10^9
  • 1 \leq N \leq 2\times 10^5
  • 1 \leq X_1 < ... < X_N \leq L-1
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

L N
X_1
:
X_N

Output

Print the longest possible total distance Takahashi walks during the process.

Sample Input 1

10 3
2
7
9

Sample Output 1

15

Takahashi walks the distance of 15 if the process goes as follows:

  • Walk a distance of 2 counter-clockwise, burn the tree at the coordinate 2 and stay there.
  • Walk a distance of 5 counter-clockwise, burn the tree at the coordinate 7 and stay there.
  • Walk a distance of 8 clockwise, burn the tree at the coordinate 9 and stay there.

Sample Input 2

10 6
1
2
3
6
7
9

Sample Output 2

27

Sample Input 3

314159265 7
21662711
77271666
89022761
156626166
160332356
166902656
298992265

Sample Output 3

1204124749