#include <bits/stdc++.h>
using namespace std;
void Read(int &x) {
  char c;
  while (c = getchar(), c != EOF)
    if (c >= '0' && c <= '9') {
      x = c - '0';
      while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0';
      ungetc(c, stdin);
      return;
    }
}
int m, n, a[100000 + 10], b[100000 * 2 + 10], f[100000 + 10], x;
void read() {
  Read(m), Read(n);
  int i;
  for (i = 1; i <= n; i++) Read(a[i]), b[i] = a[i];
  for (i = 1; i <= n; i++) b[n + i] = b[i] + m;
}
bool check(int x) {
  int i;
  f[0] = -0x7fffffff;
  f[1] = 1;
  for (i = 2; i <= n; i++) {
    f[i] = -0x7fffffff;
    if (f[i - 1] >= a[i] - 1) f[i] = a[i] + x;
    if (f[i - 1] >= a[i] - x - 1) f[i] = max(f[i], a[i]);
    if (f[i - 2] >= a[i] - x - 1) f[i] = max(f[i], a[i - 1] + x);
  }
  if (f[n] + x >= m) return 1;
  f[1] = 1 + x, f[2] = max(1 + x, a[2]);
  if (a[2] - a[1] - 1 > x + x) return 0;
  for (i = 3; i <= n; i++) {
    f[i] = -0x7fffffff;
    if (f[i - 1] >= a[i] - 1) f[i] = a[i] + x;
    if (f[i - 1] >= a[i] - x - 1) f[i] = max(f[i], a[i]);
    if (f[i - 2] >= a[i] - x - 1) f[i] = max(f[i], a[i - 1] + x);
  }
  if (f[n] >= min(m, m + a[2] - x - 1)) return 1;
  return 0;
}
int Divide_Conqure(int l, int r) {
  int mid;
  while (l < r) {
    mid = (l + r) >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  return l;
}
void solve() {
  int i, mx, p;
  mx = b[n + 1] - b[n];
  p = 1;
  for (i = 2; i <= n; i++)
    if (b[i] - b[i - 1] > mx) {
      mx = b[i] - b[i - 1];
      p = i;
    }
  a[1] = 1;
  for (i = 2; i <= n; i++) {
    a[i] = a[i - 1] + b[p + 1] - b[p];
    p++;
  }
  printf("%d\n", Divide_Conqure(0, mx - 1));
}
int main() {
  read();
  if (n == 1) {
    printf("%d\n", m - 1);
    return 0;
  }
  solve();
}
