首先二分答案固定每个 bot 的步长，然后就基本上弱于 codeforces - 1476F 了，但是还是有些不一样的地方。
假如我们是在一个序列上做 dp，不妨把原环按 $n$-$1$ 之间的间隙破开。令 $f(i)$ 表示经过决策前 $i$ 个 bots，最远能覆盖到的坐标（连续地覆盖了 $1 \sim f(i)$）。转移即分类讨论，同时令 $x$ 为当前步数：
- 前 $i-1$ 个 bots 能够覆盖到 $i-1$，那么 bot $i$ 就可以往后面倒，即 $f(i) \gets p_i+x$；
$(1)$ - 前 $i-1$ 个 bots 不能够覆盖到 $i-1$，但是可以覆盖到 $i-x-1$，那么 bot $i$ 就只能往前面倒来把序列连上。
$(2)$
乍看这样的分类讨论已经足够了，但是这个 dp 状态实际上是省略了一维的，即 $k$，$k$ 表示在 $1 \sim i$ 的 bots 当中是 bot $k$ 来将 $1 \sim f(i-1)$ 的殖民地连上的，基于贪心的策略我们把 $k$ 省掉，即尽量取靠后的 $k$。上述论证是有错误的，但大致上的意思没错，即转移如果最朴素地做并不是连续的。再看到我们的转移，如果 bot $i$ 连上了 $1 \sim f(i-2)$，则 bot $i-1$ 可以往后倒从而使 $f(i) \gets p_{i-1}+x$。
考虑环。只需要分类讨论 bot $1$ 往左往右倒即可，比较容易。
/*-ukpkmpkk-*/
#include <iostream>
#include <algorithm>
#define cmax(x, y) x = max(x, y)
using std::cin; using std::cout;
using std::min; using std::max;
int m, n, a[200100], p[100100], dp[100100];
bool chk(int cur) {
dp[1] = 0;
for (int i=2; i<=n; ++i) {
dp[i] = dp[i-1];
if (dp[i-1] >= p[i]-1) {
cmax(dp[i], p[i]+cur);
}
if (dp[i-1] >= p[i]-cur-1) {
cmax(dp[i], p[i]);
}
if (i > 2 && dp[i-2] >= p[i]-cur-1) {
cmax(dp[i], p[i-1]+cur);
}
}
if (dp[n] >= m-cur-1) return 1;
dp[2] = max(p[2], cur);
for (int i=3; i<=n; ++i) {
dp[i] = dp[i-1];
if (dp[i-1] >= p[i]-1) {
cmax(dp[i], p[i]+cur);
}
if (dp[i-1] >= p[i]-cur-1) {
cmax(dp[i], p[i]);
}
if (dp[i-2] >= p[i]-cur-1) {
cmax(dp[i], p[i-1]+cur);
}
}
if (dp[n] >= min(m-1, m+p[2]-cur-1)) return 1;
return 0;
}
signed main() {
std::ios::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n;
for (int i=1; i<=n; ++i) {
cin >> a[i];
a[i+n] = a[i]+m;
}
std::sort(a+1, a+n+n+1);
int pos = 1;
for (int i=2; i<=n; ++i) {
if (a[i+1]-a[i] > a[pos+1]-a[pos]) {
pos = i;
}
}
for (int i=1; i<=n; ++i) {
p[i] = a[i+pos];
}
for (int i=2; i<=n; ++i) {
p[i] -= p[1];
}
p[1] = 0;
int l = 0, r = a[pos+1]-a[pos]-1, mid, res = r;
while (l <= r) {
if (chk(mid = (l+r)/2)) r = mid-1, res = mid;
else l = mid+1;
}
cout << res << "\n";
}