#include <bits/stdc++.h>
using namespace std;
template <typename T>
void cmax(T& x, T y) {
  if (x < y) x = y;
}
template <typename T>
void cmin(T& x, T y) {
  if (x > y) x = y;
}
inline int read() {
  int f = 1, x = 0;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return f * x;
}
const int N = 100005;
int n, m, a[N], b[N], dp[N][2], l, r, ans, t, al;
inline bool check(int x) {
  for (int i = (1), iend = (n); i <= iend; i++) dp[i][0] = dp[i][1] = 0;
  if (b[2] == b[1] + 1)
    dp[2][0] = b[2] + x - 1;
  else if (b[2] - x <= 0)
    dp[2][0] = b[2];
  if (b[2] - x <= 0) dp[2][1] = x - 1;
  for (int i = (3), iend = (n); i <= iend; i++)
    for (int j = (0), jend = (1); j <= jend; j++) {
      if (dp[i - 1][j] >= b[i] - 1) cmax(dp[i][j], b[i] + x - 1);
      if (dp[i - 1][j] >= b[i] - x) cmax(dp[i][j], b[i]);
      if (dp[i - 2][j] >= b[i] - x) cmax(dp[i][j], b[i - 1] + x - 1);
    }
  if (dp[n][0] >= b[1] + m - x) return 1;
  if (b[2] - x <= 0 && dp[n][1] >= (b[2] - x + m)) return 1;
  return 0;
}
int main() {
  m = read(), n = read();
  for (int i = (1), iend = (n); i <= iend; i++) a[i] = read();
  if (n == 1) return printf("%d", m - 1), 0;
  for (int i = (2), iend = (n); i <= iend; i++)
    if (a[i] - a[i - 1] > t) t = a[i] - a[i - 1], al = i;
  if (a[1] + m - a[n] > t) t = a[1] - a[n] + m, al = 1;
  for (int i = (1), iend = (n); i <= iend; i++) b[i] = (a[i] - a[al] + m) % m;
  sort(b + 1, b + n + 1);
  l = 1, r = t;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid))
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%d", ans - 1);
}
