得分 : $800$ 分

问题陈述

高桥湖的周长为 $L$。在湖的周围有高桥的住所。
湖的周长上的每一点坐标介于 $0$ 到 $L$ 之间（包括 $0$ 但不包括 $L$），这是从高桥住所测量的逆时针方向的距离。

湖边有 $N$ 棵树；第 $i$ 棵树的坐标是 $X_i$。坐标 $0$ 是高桥住所的位置，那里没有树。

从他的住所出发，高桥将重复以下操作：

• 如果所有的树都被烧毁，则终止该过程。
• 指定一个方向：顺时针或逆时针。
• 沿指定方向在湖边走，直到第一次到达尚未烧毁的树的坐标。
• 当到达树的坐标时，烧毁那棵树，停留在该位置，然后返回第一步。

找出高桥在整个过程中走的最长可能的总距离。

部分得分

在此问题中，可以获得部分得分：

• 满足 $N \leq 2000$ 的输入将获得 $300$ 分。

约束条件

• $2 \leq L \leq 10^9$
• $1 \leq N \leq 2\times 10^5$
• $1 \leq X_1 < ... < X_N \leq L-1$
• 所有输入值均为整数。

输入

输入从标准输入以以下格式给出：

$L$ $N$

$X_1$

$:$

$X_N$

输出

打印高桥在整个过程中走的最长可能的总距离。

10 3
2
7
9

15

如果过程按如下方式进行，高桥走的距离为 $15$：

• 逆时针走 $2$ 的距离，烧毁坐标为 $2$ 的树，并停留在那里。
• 逆时针走 $5$ 的距离，烧毁坐标为 $7$ 的树，并停留在那里。
• 顺时针走 $8$ 的距离，烧毁坐标为 $9$ 的树，并停留在那里。

10 6
1
2
3
6
7
9

27

314159265 7
21662711
77271666
89022761
156626166
160332356
166902656
298992265

1204124749