分数: 800 点
问题陈述
高桥湖的周长为 L。在湖的周围,有湖的主人高桥的住宅。 湖圆周上的每个点都有一个坐标 0 和 L (包括 0 但不是 L),这是距高桥住所的距离,逆时针测量。
有 N 湖周围的树木;的坐标 i- 第棵树是 X_i。坐标处没有树 0,高桥的住所所在地。
从住所开始,高桥将重复以下动作:
- 如果所有树木都被烧毁,则终止该过程。
- 指定方向:顺时针或逆时针。
- 沿着指定方向绕湖行走,直到第一次到达尚未被烧毁的树的坐标。
- 当到达树的坐标时,烧毁那棵树,停留在该位置并返回第一步。
求高桥在此过程中可能行走的最长总距离。
部分分数
此问题可以获得部分分数: 通过满足以下条件的输入将获得
- 300 积分 N \leq 2000.
约束
- 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