题目描述

湖岸是一条周长为 $K$ 米的圆。湖边有 $N$ 座房屋，第 $i$ 座房屋沿顺时针方向距离参考点 $A_i$ 米，输入中位置严格递增。

你可以从任意一座房屋出发，沿湖岸向任意方向行走，也可以随时改变行走方向。要求访问所有房屋后结束行程，不必回到出发的房屋。求最少需要行走的距离。

输入格式

第一行输入两个整数 $K$ 和 $N$。

第二行输入 $N$ 个整数 $A_1, A_2, \ldots, A_N$，表示各座房屋的位置。

输出格式

输出一个整数，表示最少行走距离。

样例 1

20 3
5 10 15

10

样例 1 解释

从位置 $5$ 的房屋出发，依次经过 $10$、$15$，行走距离为 $10$。可以证明不存在更短的方案：沿圆周相邻房屋的间距依次为 $5$、$5$、$10$，任何走法都必须绕过最大的间距。

样例 2

20 3
0 5 15

10

数据范围

• $2 \le K \le 10^6$；
• $2 \le N \le 2 \times 10^5$；
• $0 \le A_1 < A_2 < \cdots < A_N < K$；
• 所有输入均为整数。

本题共 25 个测试点，每个测试点 4 分，按测试点独立计分。

特殊性质 A：沿圆周相邻两座房屋之间的间距全部相等（包括最后一座房屋绕过参考点回到第一座房屋的间距）。