#include <bits/stdc++.h>
using namespace std;
int n, m, L, R, p;
int f[101000], A[101000], d[101000];
bool judge(int mid) {
  for (int i = 1; i <= n; i++)
    if (mid * 2 < d[i] - 1) return false;
  f[1] = 0;
  memset(f, 0, sizeof(f));
  for (int i = 1; i < n; i++) {
    bool fl = false;
    if (f[i] >= d[i] - 1) f[i + 1] = max(mid, f[i + 1]), fl = true;
    if (f[i] >= d[i] - mid - 1)
      f[i + 1] = max(f[i + 1], f[i] - d[i]), fl = true;
    if (i > 1 && f[i - 1] >= d[i] + d[i - 1] - 1)
      f[i + 1] = max(f[i + 1], mid), fl = true;
    if (i > 1 && f[i - 1] >= d[i] + d[i - 1] - mid - 1)
      f[i + 1] = max(f[i + 1], mid - d[i]), fl = true;
    if (!fl) break;
  }
  if (f[n] + mid >= d[n] - 1) return true;
  memset(f, 0, sizeof(f));
  f[1] = mid;
  f[2] = max(0, f[1] - d[1]);
  for (int i = 2; i < n; i++) {
    bool fl = false;
    if (f[i] >= d[i] - 1) f[i + 1] = max(mid, f[i + 1]), fl = true;
    if (f[i] >= d[i] - mid - 1)
      f[i + 1] = max(f[i + 1], f[i] - d[i]), fl = true;
    if (i > 1 && f[i - 1] >= d[i] + d[i - 1] - 1)
      f[i + 1] = max(f[i + 1], mid), fl = true;
    if (i > 1 && f[i - 1] >= d[i] + d[i - 1] - mid - 1)
      f[i + 1] = max(f[i + 1], mid - d[i]), fl = true;
    if (!fl) break;
  }
  if (f[n] + mid >= d[n] + d[1] - 1) return true;
  return false;
}
int main() {
  scanf("%d\n%d", &m, &n);
  for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
  if (n == 1) {
    printf("%d\n", m - 1);
    return 0;
  }
  sort(A + 1, A + n + 1);
  A[0] = A[n];
  for (int i = 1; i <= n; i++) d[i] = (A[i] - A[i - 1] + m) % m;
  for (int i = 1; i <= n; i++) {
    if (R < d[i]) p = i;
    R = max(R, d[i]);
  }
  rotate(d + 1, d + p + 1, d + n + 1);
  while (L < R) {
    int mid = (L + R) >> 1;
    if (judge(mid))
      R = mid;
    else
      L = mid + 1;
  }
  printf("%d\n", L);
  return 0;
}
