#include <bits/stdc++.h>
using namespace std;
inline int read() {
  static char ch;
  bool sgn = false;
  while (ch = getchar(), ch < '0' || ch > '9')
    if (ch == '-') sgn = true;
  int res = ch - 48;
  while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
  return sgn ? -res : res;
}
const int N = 200005;
int n, m, M, p, s, a[N], b[N], f[N];
bool check(int x) {
  f[1] = 1;
  f[0] = -INT_MAX;
  for (int i = 2; i <= n; i++) {
    f[i] = -INT_MAX;
    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] >= m - x) return 1;
  f[1] = 1 + x;
  f[2] = max(1 + x, a[2]);
  if (a[2] - a[1] - 1 > x + x) return 0;
  for (int i = 3; i <= n; i++) {
    f[i] = -INT_MAX;
    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 main() {
  m = read();
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
  for (int i = n + 1; i <= n + n; i++) b[i] = b[i - n] + m;
  if (n == 1) {
    cout << m - 1;
    return 0;
  }
  M = a[1] - a[n] + m;
  p = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i] - a[i - 1] > M) {
      M = a[i] - a[i - 1];
      p = i;
    }
  }
  M--;
  s = a[1] = 1;
  for (int i = 2; i <= n; i++) {
    p++;
    s += b[p] - b[p - 1];
    a[i] = s;
  }
  int l = 0, r = M;
  while (l < r) {
    int mid = l + r >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid;
    if (l + 1 == r) {
      if (check(l))
        r--;
      else
        l++;
    }
  }
  cout << l;
}
