#include <bits/stdc++.h>
using namespace std;
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et() {
  puts("-1");
  exit(0);
}
int p[200105];
int dp[200105];
bool ck(int mid) {
  for (int k = 1; k <= 2 && k <= n; k++) {
    if (k == 1) {
      dp[1] = 0;
    } else {
      dp[1] = mid;
      dp[2] = max(mid, p[2]);
    }
    for (int i = k + 1; i <= n; i++) {
      dp[i] = dp[i - 1];
      if (dp[i - 1] >= p[i] - 1) dp[i] = max(dp[i], p[i] + mid);
      if (dp[i - 1] >= p[i] - mid - 1) dp[i] = max(dp[i], p[i]);
      if (i >= k + 2 && dp[i - 2] >= p[i] - mid - 1)
        dp[i] = max(dp[i], p[i - 1] + mid);
    }
    if (dp[n] >= min(m - 1, p[k] - mid - 1 + m)) return 1;
  }
  return 0;
}
void fmain() {
  scanf("%d%d", &m, &n);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    scanf("%d", p + i);
    p[i + n] = p[i] + m;
  }
  if (n == 1) {
    printf("%d\n", m - 1);
    return;
  }
  int r = 0, tar;
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    if (r < p[i + 1] - p[i]) {
      r = p[i + 1] - p[i];
      tar = i;
    }
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++) p[i] = p[tar + i];
  for (int x = p[1], i = 1; i <= n; i++) {
    p[i] -= x;
  }
  int l = -1;
  while (l + 1 < r) {
    int mid = (l + r) / 2;
    if (ck(mid))
      r = mid;
    else
      l = mid;
  }
  printf("%d\n", r);
}
int main() {
  fmain();
  return 0;
}
