#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, inf = 2e9;
int n, m, mx, pos;
int a[N], p[N], dp[N][2];
bool check(int x) {
  for (int j = 0; j <= 1; j++) {
    if (j) {
      dp[1][0] = -inf, dp[1][1] = x;
      if (p[2] <= x + 1)
        dp[2][0] = max(x, p[2]);
      else
        dp[2][0] = -inf;
    } else
      dp[1][0] = 0, dp[1][1] = -inf;
    for (int i = j + 2; i <= n; i++) {
      dp[i][0] = dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]);
      if (max(dp[i - 1][0], dp[i - 1][1]) + 1 >= p[i]) dp[i][1] = p[i] + x;
      if (p[i] - x - 1 <= dp[i - 1][0]) dp[i][0] = max(dp[i - 1][0], p[i]);
      if (p[i] - x - 1 <= dp[i - 1][1])
        dp[i][0] = max(dp[i][0], max(p[i], p[i - 1] + x));
    }
    int tt = max(dp[n][0], dp[n][1]);
    if (j && p[2] - x + m <= tt + 1)
      return 1;
    else if (!j && -x + m <= tt + 1)
      return 1;
  }
  return 0;
}
int main() {
  scanf("%d%d", &m, &n);
  if (n == 1) {
    printf("%d", m - 1);
    return 0;
  }
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) {
    int dis = (i == 1) ? a[1] - a[n] + m : a[i] - a[i - 1];
    if (dis > mx) mx = dis, pos = i;
  }
  for (int i = 1; i <= n; i++) {
    int rt = pos + i - 1;
    if (rt > n) rt -= n;
    p[i] = (a[rt] - a[pos] + m) % m;
  }
  int l = 0, r = mx - 1, ans = mx - 1;
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(mid))
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%d", ans);
}
