#include <bits/stdc++.h>
using namespace std;
long long n, m, f[1000000][2], P[1000000], p[1000000];
long long ans, mx, pos;
long long read() {
  long long x = 0, k = 1;
  char c;
  c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') k = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * k;
}
bool Check(long long x) {
  for (long long j = 0; j <= 1; j++) {
    f[1][0] = j ? -99999999999LL : P[1];
    f[1][1] = j ? P[1] + x : -99999999999LL;
    if (j) {
      if (P[1] + x + 1 >= P[2]) f[2][0] = max(P[1] + x, P[2]);
      f[2][1] = -99999999999LL;
    }
    for (long long i = j + 2; i <= n; i++) {
      f[i][0] = f[i][1] = max(f[i - 1][0], f[i - 1][1]);
      if (max(f[i - 1][1], f[i - 1][0]) + 1 >= P[i]) f[i][1] = P[i] + x;
      if (P[i] - x - 1 <= f[i - 1][0]) f[i][0] = max(f[i - 1][0], P[i]);
      if (P[i] - x - 1 <= f[i - 1][1])
        f[i][0] = max(f[i - 1][1], max(P[i], P[i - 1] + x));
    }
    long long t = max(f[n][0], f[n][1]);
    if (j && t + 1 >= P[2] + m - x)
      return 1;
    else if (!j && t + 1 >= P[1] + m - x)
      return 1;
  }
  return 0;
}
signed main() {
  m = read(), n = read();
  if (n == 1) {
    printf("%I64d\n", m - 1);
    return 0;
  }
  for (long long i = 1; i <= n; i++) p[i] = read();
  for (long long i = 1; i <= n; i++) {
    long long dis;
    dis = p[i] - p[i - 1];
    if (i == 1) dis = p[i] + m - p[n];
    if (dis > mx) mx = dis, pos = i;
  }
  for (long long i = 1; i <= n; i++) {
    long long t = i - 1 + pos;
    if (t > n) t -= n;
    P[i] = p[t];
    P[i] -= p[pos];
    if (P[i] < 0) P[i] += m;
  }
  long long l = 0, r = m - 1;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    if (Check(mid))
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%I64d\n", ans);
  return 0;
}
