题目描述

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

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

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

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

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

输入格式

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

$L$ $N$ $X_1$ $:$ $X_N$

输出格式

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

题目大意

高桥湖是周长为 $L$ 的一个首尾相接的圆，圆上整点标为$0, 1, 2, ..., L-1$.

在湖边有 $N$ 颗树，分别在距离起点顺时针数 $X_1, X_2,...,X_n$ 的位置上。保证位置 $0$ 没有树。

高桥君初始在位置 $0$ 上，每次可以选择顺时针或逆时针走到第一颗还没有被点燃过的树并将其点燃，直到所有树都被点燃为止。

求高桥君最长的移动距离。

10 3
2
7
9

15

10 6
1
2
3
6
7
9

27

314159265 7
21662711
77271666
89022761
156626166
160332356
166902656
298992265

1204124749

提示

制約

• $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$ 点が得られる。

Sample Explanation 1

以下のような行動で、高橋君は距離 $15$ を歩きます。 - 反時計回りに距離 $2$ ぶんだけ歩き、座標 $2$ にある木を燃やして立ち止まる。 - 反時計回りに距離 $5$ ぶんだけ歩き、座標 $7$ にある木を燃やして立ち止まる。 - 時計回りに距離 $8$ ぶんだけ歩き、座標 $9$ にある木を燃やして立ち止まる。