题目描述

高桥湖的周长为 $L$。在高桥湖的周围有高桥君的家，作为湖的所有者。湖周上的每一个点都可以用从高桥君家出发，沿逆时针方向测量的距离来确定其坐标，坐标为 $0$ 以上且小于 $L$ 的实数。

湖的周围长有 $N$ 棵树。第 $i$ 棵树长在坐标 $X_i$ 处。高桥君家的坐标 $0$ 处没有树。

高桥君从自己的家出发，重复以下行为：

• 如果所有的树都已经被烧掉，则结束。
• 指定顺时针或逆时针的方向。
• 沿指定方向在湖的周围行走，直到第一次到达尚未烧掉的树所在的坐标为止。
• 到达有树的坐标后，将该树烧掉并停留在原地，然后回到最初的步骤。

请你求出，在这一系列行为中，高桥君所行走的距离总和的最大值。

输入格式

输入通过标准输入按以下格式给出。

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

输出格式

请输出高桥君所行走的距离总和的最大值。

样例 1

输入

10 3
2
7
9

输出

15

样例 2

输入

10 6
1
2
3
6
7
9

输出

27

样例 3

输入

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 < \cdots < X_N \leq L-1$
• 输入均为整数

部分得分

本题设有部分得分。

• 对于 $N \leq 2000$ 的输入，答对可得 $300$ 分。

样例说明 1

按照如下方式行动，高桥君总共行走了 $15$ 的距离。

• 逆时针行走 $2$ 的距离，到达坐标 $2$，烧掉该树并停下。
• 逆时针行走 $5$ 的距离，到达坐标 $7$，烧掉该树并停下。
• 顺时针行走 $8$ 的距离，到达坐标 $9$，烧掉该树并停下。

由 ChatGPT 4.1 翻译