#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int INF = 0x3f3f3f3f;
int dis[MAXN + 10], pos[MAXN + 10], f[MAXN + 10], Max, m, n;
bool check(const int& x) {
  if (x >= dis[1] - 1) return true;
  if (2 * x < dis[1] - 1) return false;
  f[1] = 0;
  for (int i = 2; i <= n; i++) {
    f[i] = -INF;
    if (f[i - 1] >= pos[i] - 1) f[i] = pos[i] + x;
    if (f[i - 1] >= pos[i] - 1 - x) f[i] = max(f[i], pos[i]);
    if (i > 2 && f[i - 2] >= pos[i] - 1 - x) f[i] = max(pos[i - 1] + x, f[i]);
  }
  if (f[n] + x >= m - 1) return true;
  f[1] = x, f[2] = max(x, pos[2]);
  for (int i = 3; i <= n; i++) {
    f[i] = -INF;
    if (f[i - 1] >= pos[i] - 1) f[i] = pos[i] + x;
    if (f[i - 1] >= pos[i] - 1 - x) f[i] = max(f[i], pos[i]);
    if (f[i - 2] >= pos[i] - 1 - x) f[i] = max(pos[i - 1] + x, f[i]);
  }
  if (f[n] >= min(m - 1, pos[2] + m - 1 - x)) return true;
  return false;
}
int tmp[MAXN + 10];
void _rotate(int* arr, int mid, int len) {
  int cnt = 0;
  for (int i = mid; i <= len; i++) tmp[++cnt] = arr[i];
  for (int i = 1; i < mid; i++) tmp[++cnt] = arr[i];
  for (int i = 1; i <= len; i++) arr[i] = tmp[i];
}
int main() {
  scanf("%d%d", &m, &n);
  if (n == 1) {
    printf("%d\n", m - 1);
    return 0;
  }
  for (int i = 1; i <= n; i++) scanf("%d", &pos[i]);
  sort(pos + 1, pos + 1 + n);
  pos[0] = pos[n];
  int p;
  for (int i = 1; i <= n; i++) {
    dis[i] = (pos[i] - pos[i - 1] + m) % m;
    if (dis[i] > Max) p = i;
    Max = max(Max, dis[i]);
  }
  _rotate(pos, p, n);
  _rotate(dis, p, n);
  int eff = pos[1];
  for (int i = 1; i <= n; i++) pos[i] = (pos[i] - eff + m) % m;
  int L = 1, R = Max - 1, ans = 0;
  while (L <= R) {
    int mid = (L + R) >> 1;
    if (check(mid)) {
      ans = mid;
      R = mid - 1;
    } else
      L = mid + 1;
  }
  printf("%d\n", ans);
  return 0;
}
