#include <bits/stdc++.h>
using namespace std;
int m, n;
const int N = 300000;
int f[N], ai[N], bi[N], mx;
int check(int x) {
  f[1] = 1;
  for (int i = 2; i <= n; ++i) {
    f[i] = -1e9;
    if (f[i - 1] >= bi[i] - 1) f[i] = max(f[i], bi[i] + x);
    if (f[i - 1] >= bi[i] - x - 1) f[i] = max(f[i], bi[i]);
    if (f[i - 2] >= bi[i] - x - 1 && i != 2) f[i] = max(f[i], bi[i - 1] + x);
  }
  if (f[n] >= bi[1] - x - 1 + m) return 1;
  if (f[n - 1] >= bi[1] - x - 1 + m) return 1;
  if (bi[1] + x < bi[2] - x - 1) return 0;
  f[1] = 0;
  f[2] = max(bi[2], bi[1] + x);
  for (int i = 3; i <= n; ++i) {
    f[i] = -1e9;
    if (f[i - 1] >= bi[i] - 1) f[i] = max(f[i], bi[i] + x);
    if (f[i - 1] >= bi[i] - x - 1) f[i] = max(f[i], bi[i]);
    if (f[i - 2] >= bi[i] - x - 1 && i != 2) f[i] = max(f[i], bi[i - 1] + x);
  }
  if (f[n] >= min(bi[1], bi[2] - x) - 1 + m) return 1;
  if (f[n - 1] >= min(bi[1], bi[2] - x) - 1 + m) return 1;
  return 0;
}
int main() {
  ios ::sync_with_stdio(0);
  cin >> m >> n;
  for (int i = 1; i <= n; ++i) cin >> ai[i];
  ai[n + 1] = ai[1] + m;
  for (int i = 1; i <= n; ++i) mx = max(mx, ai[i + 1] - ai[i]);
  for (int i = 1; i <= n; ++i)
    if (ai[i + 1] - ai[i] == mx) {
      int c = 0;
      for (int j = i + 1; j <= n; ++j) bi[++c] = ai[j] - ai[i + 1] + 1;
      for (int j = 1; j <= i; ++j) bi[++c] = ai[j] + m - ai[i + 1] + 1;
      break;
    }
  if (n == 1) cout << m - 1 << endl, exit(0);
  int l = 0, r = m - bi[n];
  while (l < r) {
    int md = (l + r) / 2;
    if (check(md))
      r = md;
    else
      l = md + 1;
  }
  cout << l << endl;
}
