CF713E.Sonya Partymaker

Owl Sonya decided to become a partymaker. To train for this role she gather all her owl friends in the country house. There are m chairs located in a circle and consequently numbered with integers from 1 to m. Thus, chairs i and i + 1 are neighbouring for all i from 1 to m - 1. Chairs 1 and m are also neighbouring. Some chairs are occupied by her friends. There are n friends in total. No two friends occupy the same chair. Rules are the following:

1. Each participant removes from the game the chair he is currently sitting on.
2. Each of the participants choose a direction that she will follow: clockwise (indices increase, from m goes to 1) and counter-clockwise (indices decrease, from 1 goes to m). This direction may coincide or be different for any pair of owls.
3. Each turn all guests move one step in the chosen directions. If some guest move to the position with a chair there, he removes this chair from the game.
4. Game ends if there are no more chairs left in the game.

Owls are very busy and want to get rid of the game as soon as possible. They cooperate to pick the direction. Your goal is to find the minimum number o moves required to finish the game.

猫头鹰索尼娅决定成为一名派对策划师。为了训练这一角色，她把所有猫头鹰朋友召集到乡间别墅。别墅里有 $m$ 把椅子围成一个圆圈，并按顺时针方向依次编号为 $1$ 到 $m$。因此，对于所有 $i = 1, 2, \dots, m-1$，椅子 $i$ 和 $i+1$ 是相邻的；此外，椅子 $1$ 和 $m$ 也相邻。其中一些椅子已被她的朋友们占据，共有 $n$ 位朋友，且任意两位朋友不会坐在同一把椅子上。游戏规则如下：

1. 每位参与者移除自己当前所坐的那把椅子；
2. 每位参与者选择一个移动方向：顺时针（编号递增，从 $m$ 继续到 $1$）或逆时针（编号递减，从 $1$ 继续到 $m$）。不同猫头鹰所选方向可以相同，也可以不同；
3. 每一轮中，所有参与者均朝各自选定的方向移动一步；若某位参与者移动到了一把尚存的椅子所在的位置，则他将该椅子从游戏中移除；
4. 当游戏中不再剩下任何椅子时，游戏结束。

猫头鹰们非常忙碌，希望尽快结束游戏。它们会相互协作以共同决定每位参与者应选择的方向。你的任务是求出结束游戏所需的最少轮数。

The first line of the input contains a single integer m (1 ≤ m ≤ 109) — the length of the circle.

The second line contains a single integer n (1 ≤ n ≤ 100 000) — the number of friends.

Last line contains an increasing sequence of n integers a__i (1 ≤ a__i ≤ m) — initial positions of all owls.

输入的第一行包含一个整数 $m$（$1 \leq m \leq 10^9$）—— 圆的长度。

第二行包含一个整数 $n$（$1 \leq n \leq 100\,000$）—— 朋友的数量。

最后一行包含一个严格递增的 $n$ 个整数序列 $a_i$（$1 \leq a_i \leq m$）—— 所有猫头鹰的初始位置。

Print the minimum number of move required to finish the game. Note, that 0 also may be an answer.

输出完成游戏所需的最少移动次数。注意，答案也可能是 0。

In the first sample, it's possible if all owls will move clockwise, i.e. in the direction of increasing indices.

In the sample, first owl has to move clockwise, while the second — counterclockwise.

In the third sample, the first and the fourth owls should move counterclockwise, while the third and the sixth — clockwise. The second and the firth may move in any direction.

在第一个样例中，如果所有猫头鹰都顺时针移动（即沿索引递增的方向），则该情况是可行的。

在该样例中，第一只猫头鹰必须顺时针移动，而第二只猫头鹰必须逆时针移动。

在第三个样例中，第一只和第四只猫头鹰应逆时针移动，而第三只和第六只猫头鹰应顺时针移动。第二只和第五只猫头鹰可朝任意方向移动。