You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

为了构建鼠类命运共同体

高贵的土拨鼠与愚蠢的人类展开了新一轮的征战.

Description

愚蠢的人类向我们发起了进攻, 毫无疑问, 进攻软弱的像一坨屎.

我们的防御圈可以看作是一个周长为$c$的圆, 在圆上有$n$个火力输出点.

从圆上某一个位置出发, 在行走$a_i$距离后, 会有一个火力点$i$.

$a_i$表示从出发点到$i$点的距离

现在你可以从圆上任意一点出发, 请问你能否找到一条最短的路径, 使得每个节点都访问一次? 这个最短的路径是多少.

Format

Input

第1行两个整数$c, n$, $c$表示圆的周长, $n$表示节点个数

第2行输入$n$个整数$a_i$, 表示你从某一点出发后, 遇到的每个火力点距离你出发点的位置.

注意: 顺序有可能混乱

Output

输出一个整数, 表示你可以访问的最短路径

Samples

20 3
10 15 5

10

样例解释

你可以选则从3点出发, 走到1点, 再走到2点, 一共经历10的路程

Limitation

$2 <= c <= 10^9$

$2 <= n <= 2*10^5$

$(0 <= a_i < c)$