#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010, inf = 1e9 + 233;
int n, m;
int f[maxn][2], a[maxn], b[maxn];
template <typename T>
inline void read(T &k) {
  int f = 1;
  k = 0;
  char c = getchar();
  while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
  while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
  k *= f;
}
inline bool check(int mid) {
  f[0][0] = f[0][1] = 0;
  for (int T = 1; T <= 2; T++) {
    int pre0 = f[0][0], pre1 = f[0][1];
    memset(f, 0x3f, sizeof(f));
    f[0][0] = pre0;
    f[0][1] = pre1;
    for (int i = 0; i < n; i++) {
      if (f[i][0] <= 0)
        f[i][1] = -mid;
      else if (f[i][0] <= mid)
        f[i][1] = min(f[i][1], 0);
      else
        return 0;
      if (f[i][0] > 0) {
        int len = a[i + 1] - a[i] + f[i][0];
        if (len <= mid) f[i + 1][1] = min(f[i + 1][1], a[i + 1] - a[i] - mid);
      }
      f[i + 1][0] = a[i + 1] - a[i] - 1 + f[i][1];
    }
    if (f[n][0] <= pre0 && f[n][1] <= pre1) return 1;
    f[0][0] = f[n][0];
    f[0][1] = f[n][1];
  }
  return 0;
}
int main() {
  read(m);
  read(n);
  for (int i = 0; i < n; i++) read(a[i]);
  int mxlen = 0, mxpos = 0;
  for (int i = 0; i < n - 1; i++)
    if (mxlen < a[i + 1] - a[i]) mxlen = a[i + 1] - a[i], mxpos = i;
  if (a[0] - a[n - 1] + m > mxlen) mxlen = a[0] - a[n - 1] + m, mxpos = n - 1;
  for (int i = 0; i < mxpos; i++) b[i + n - mxpos] = a[i] + m;
  for (int i = mxpos; i < n; i++) b[i - mxpos] = a[i];
  memcpy(a, b, sizeof(b));
  a[n] = a[0] + m;
  int l = 0, r = mxlen;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  printf("%d\n", l);
}
