问题描述

高桥湖的周长为$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$

输出

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

样例输入 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