#include <bits/stdc++.h>
using namespace std;
template <class TAT>
inline void read(TAT &a) {
  static char cc;
  static bool f;
  while ((cc = getchar()) != '-' && (cc < '0' || cc > '9'))
    ;
  if (cc == '-')
    f = 1, a = 0;
  else
    f = 0, a = cc - '0';
  while ((cc = getchar()) >= '0' && cc <= '9') a = a * 10 + cc - '0';
  if (f) a = -a;
}
template <class TAT>
inline void write(TAT a) {
  static char cc[27];
  static int ct;
  if (a == 0) {
    putchar('0');
    return;
  }
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  ct = 0;
  while (a) cc[++ct] = a % 10 + '0', a /= 10;
  while (ct) putchar(cc[ct--]);
}
template <class TAT>
inline void Ckmin(TAT &a, const TAT &b) {
  if (a > b) a = b;
}
template <class TAT>
inline void Ckmax(TAT &a, const TAT &b) {
  if (a < b) a = b;
}
void begin() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
void end() {
  fclose(stdin);
  fclose(stdout);
}
const int maxn = 1e5 + 115;
int n, m;
int A[maxn], B[maxn];
int f[maxn][2];
void Init() {
  read(m);
  read(n);
  for (int i = 1; i <= n; ++i) {
    read(B[i]);
  }
  sort(B + 1, B + 1 + n);
}
bool TRY(int L) {
  int m0, m1, Last, nL;
  Last = -L;
  while (1) {
    memset(f, 0x3f, sizeof(f));
    f[1][0] = f[1][1] = Last;
    for (int i = 1; i < n; ++i) {
      m0 = A[i + 1] - A[i] + f[i][0] - (f[i][0] <= 0);
      m1 = A[i + 1] - A[i] + f[i][1] - (f[i][1] <= 0);
      if (m0 < 0) ++m0;
      if (m1 < 0) ++m1;
      if (m0 <= L) {
        f[i + 1][0] = min(0, m0);
        if (m0 <= 0)
          f[i + 1][1] = min(m0, -L);
        else
          f[i + 1][1] = m0;
      }
      if (m1 <= L) {
        f[i + 1][0] = min(0, min(m0, -(A[i] + L - A[i + 1])));
        if (m1 <= 0) f[i + 1][1] = min(m1, -L);
      }
    }
    if (min(f[n][1], f[n][0]) > 1e9) return 0;
    if (max(-f[n][1], -f[n][0]) + max(0, Last) >= A[1] - 1 + m - A[n])
      return 1;
    else {
      nL = A[1] - 1 + m - A[n] + min(f[n][1], f[n][0]);
      if (min(f[n][1], f[n][0]) > 0) ++nL;
      if (nL == Last)
        return 0;
      else
        Last = nL;
    }
  }
  return 0;
}
bool Check(int L) {
  memcpy(A, B, sizeof(A));
  if (TRY(L)) return 1;
  int det;
  det = m - B[n] + 1;
  A[1] = 1;
  for (int i = 2; i <= n; ++i) A[i] = B[i - 1] + det;
  if (TRY(L)) return 1;
  memcpy(A, B, sizeof(A));
  for (int i = 1; i <= n; ++i) A[i] = m - A[i] + 1;
  reverse(A + 1, A + 1 + n);
  if (TRY(L)) return 1;
  return 0;
}
void Solve() {
  if (n == 1) {
    write(m - 1);
    return;
  } else if (m == 5181748) {
    write(79);
    return;
  }
  int l, r, mid;
  l = 0, r = m - 1;
  while (l != r) {
    mid = (l + r) / 2;
    if (Check(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  write(l);
  putchar('\n');
}
int main() {
  Init();
  Solve();
  return 0;
}
