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.

Description

9月14日举办了全国中学生数学奥林匹克竞赛（预赛）。

今天是所有数学竞赛学生的重要节日。

无数学生来到华附参加比赛。华附可以看成一个长度为 n 的大圆环。环上有 $n$ 个位置：1,2,3,...,n。

每个单位时间，学生们可以顺时针或逆时针移动一个单位位置，或者不动。 只有一整个单位时间能移动，不存在半个单位时间移动半个单位距离。

从位置1顺时针走1个单位时间，到达位置2。

从位置2顺时针走1个单位时间，到达位置3。以此类推。

从位置n顺时针走1个单位时间，到达位置1。

从位置1逆时针走1个单位时间，到达位置n。

现在有 m 个学生在华附，他们的位置分别为 $a_1, a_2, ..., a_m$。

赛后，他们将选择一个位置集合，一起庆祝。问最短需要多少时间他们能聚集到同一个地点。

Input

第一行2个正整数 n 和 m。

接下来 m 行，每行1个整数，表示第 i 个学生的位置。

Output

集合需要的最短时间单位。必须是整数。

Samples

5 2
3 
1

1

在位置2集合。在位置1的学生顺时针走，在位置3的学生逆时针走。

10 2
1 
9

1

在位置10集合。

Limitation

对于30%的数据 $2 \le m \le 3$

另有30%的数据 $n \le 1000$

对于100%的数据 $1 \le n \le 10^9 , 1\le m \le 10^5$, $1 \le a_i \le n$