CF713E Sonya Partymaker

猫头鹰 Sonya 决定成为一名派对组织者。为此，她召集了她所有的猫头鹰朋友来到乡村别墅。别墅里有 $m$ 把椅子，这些椅子按顺时针顺序围成一个圆圈，并依次编号为 $1$ 到 $m$。因此，对于所有 $i$ 满足 $1 \leq i \leq m-1$，椅子 $i$ 和椅子 $i+1$ 是相邻的，同时椅子 $1$ 和椅子 $m$ 也是相邻的。有些椅子上已经坐了她的朋友们，共有 $n$ 个朋友，没有两个朋友坐在同一把椅子上。游戏的规则如下： 1. 每位参与者会将自己当前所坐的椅子从游戏中移除（即这把椅子消失）。 2. 每位参与者可以选择一个她接下来要沿着前进的方向：顺时针（编号增加，从 $m$ 到 $1$）或逆时针（编号减少，从 $1$ 到 $m$）。每只猫头鹰选择的方向可以相同，也可以不同。 3. 每一轮，所有参与者都会按照自己选择的方向移动一格。如果某位参与者走到的格子上有椅子，这把椅子会被移除。 4. 当所有椅子都被移除时，游戏结束。 猫头鹰们都很忙，她们希望尽快地结束游戏。她们会协作选择行动的方向。你的目标是求出移除所有椅子所需的最少移动次数。

第一行输入一个整数 $m$（$1 \leq m \leq 10^{9}$），表示圆上椅子的数量。 第二行输入一个整数 $n$（$1 \leq n \leq 100000$），表示朋友的数量。 最后一行输入 $n$ 个递增的整数 $a_i$（$1 \leq a_i \leq m$），表示每只猫头鹰的初始位置。

输出移除所有椅子所需的最少移动次数。注意，答案也可能是 $0$。

在第一个样例中，如果所有猫头鹰都朝顺时针方向（即编号递增的方向）移动，就可以达成最优。 在样例中，第一只猫头鹰应该顺时针移动，第二只猫头鹰应该逆时针移动。 在第三个样例中，第一只和第四只猫头鹰应当逆时针移动，第三只和第六只顺时针移动。第二只和第五只可以任选方向。 由 ChatGPT 5 翻译