#include <bits/stdc++.h>
using namespace std;
inline long long rd() {
  long long x = 0;
  int ch = getchar(), f = 1;
  while (!isdigit(ch) && (ch != '-') && (ch != EOF)) ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void rt(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10)
    rt(x / 10), putchar(x % 10 + '0');
  else
    putchar(x + '0');
}
const int maxn = 100005;
int n, m, a[maxn];
long long f[maxn][2];
bool solve1(long long x) {
  memset(f, 40, sizeof f);
  f[2][1] = a[2] - a[1] - 1;
  for (int i = 2; i <= (int)n; i++) {
    if (f[i][1] <= 0)
      f[i][0] = min(f[i][0], -x);
    else {
      if (f[i][1] > x) return 0;
      f[i][0] = min(f[i][0], 0ll);
      if (x >= a[i + 1] - a[i] + f[i][1])
        f[i + 1][0] = min(f[i + 1][0], a[i + 1] - a[i] - x);
    }
    f[i + 1][1] = min(f[i + 1][1], f[i][0] + a[i + 1] - a[i] - 1);
  }
  if (f[n][1] <= 0 && a[n] + 2 * x - m >= 0) return 1;
  if ((f[n - 1][1] <= 0 || x >= a[n] - a[n - 1] + f[n - 1][1]) &&
      a[n - 1] + 2 * x - m >= 0)
    return 1;
  return 0;
}
bool solve2(long long x) {
  memset(f, 40, sizeof f);
  if (a[2] - a[1] >= x) return 0;
  f[2][0] = a[2] - a[1] - x;
  for (int i = 2; i <= (int)n; i++) {
    if (f[i][1] <= 0)
      f[i][0] = min(f[i][0], -x);
    else {
      if (f[i][1] > x && i != 2) return 0;
      f[i][0] = min(f[i][0], 0ll);
      if (x >= a[i + 1] - a[i] + f[i][1])
        f[i + 1][0] = min(f[i + 1][0], a[i + 1] - a[i] - x);
    }
    f[i + 1][1] = min(f[i + 1][1], f[i][0] + a[i + 1] - a[i] - 1);
  }
  if (f[n][1] <= 0 && a[n] + 2 * x - m >= a[2] - 1) return 1;
  if ((n == 2 || x >= a[n] - a[n - 1] + f[n - 1][1] - (f[n - 1][1] >= 0)) &&
      a[n - 1] + 2 * x - m >= a[2] - 1)
    return 1;
  return 0;
}
int main() {
  m = rd(), n = rd();
  if (n == m) return puts("0"), 0;
  if (n == 1) return rt(m - 1), 0;
  for (int i = 1; i <= (int)n; i++) a[i] = rd();
  int mxn = a[1] + m - a[n] - 1, nd = 1;
  for (int i = 1; i <= (int)n - 1; i++)
    if (a[i + 1] - a[i] - 1 > mxn) mxn = a[i + 1] - a[i] - 1, nd = i + 1;
  for (int i = 1; i <= (int)n; i++)
    if (i != nd) a[i] -= a[nd] - 1, a[i] += a[i] < 1 ? m : 0;
  a[nd] = 1;
  sort(a + 1, a + n + 1);
  int l = 1, r = a[1] + m - a[n] - 2;
  while (l < r) {
    int mid = l + r >> 1;
    if (solve1(mid) || solve2(mid))
      r = mid;
    else
      l = mid + 1;
  }
  if (solve1(l) || solve2(l))
    rt(l);
  else
    rt(a[1] + m - a[n] - 1);
  putchar('\n');
}
