#include <bits/stdc++.h>
using namespace std;
const long long N = 200100;
const long long oo = 2e18;
long long i, n, m, l, r, mid;
long long a[N], f[N][2];
inline long long read() {
  long long x = 0, f = 0, c = getchar();
  for (; c > '9' || c < '0'; f = c == '-', c = getchar())
    ;
  for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
  return f ? -x : x;
}
bool check(long long x) {
  long long i, k1, k2, start0 = 0, start1 = 0;
  while (start0 <= x) {
    if (!start0)
      f[0][0] = -x;
    else
      f[0][0] = start0;
    f[0][1] = start1;
    for (i = 1; i <= n; i++) f[i][0] = oo, f[i][1] = 0;
    for (i = 0; i < n; i++) {
      if (f[i][0] > x) return 0;
      if (f[i][0] > 0)
        k1 = a[i + 1] - a[i] + f[i][0];
      else {
        k1 = a[i + 1] - a[i] - x;
        if (k1 > 0) k1--;
      }
      if (k1 < 0)
        f[i + 1][0] = -x;
      else
        f[i + 1][0] = min(f[i + 1][0], k1);
      k2 = a[i + 1] - a[i] + f[i][1];
      if (k2 > 0) k2--;
      if (k2 < 0)
        f[i + 1][0] = -x;
      else
        f[i + 1][0] = min(f[i + 1][0], k2);
      if (k1 <= x) f[i + 1][1] = min(f[i + 1][1], a[i + 1] - a[i] - x);
      f[i + 1][1] = min(f[i + 1][1], k2);
    }
    if (f[n][0] <= start0 && f[n][1] <= start1) return 1;
    start0 = f[n][0];
    start1 = f[n][1];
  }
  return 0;
}
signed main() {
  m = read();
  n = read();
  for (i = 0; i < n; i++) a[i] = read();
  a[n] = a[0] + m;
  sort(a, a + n + 1);
  l = 0;
  r = m - n;
  while (l < r) {
    mid = (l + r - 1) >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  printf("%I64d\n", l);
}
