#include <bits/stdc++.h>
using namespace std;
const long long inf = INT_MAX, df = 3e5 + 7;
long long i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, dp[df], pos[df],
    a[df];
inline long long read() {
  long long x = 0, y = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') y = (ch == '-') ? -1 : 1, ch = getchar();
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  return x * y;
}
bool chk(long long x) {
  dp[1] = 0;
  for (long long i = (2); i <= (n); ++i) {
    dp[i] = dp[i - 1];
    if (dp[i - 1] >= pos[i] - 1) dp[i] = max(dp[i], pos[i] + x);
    if (dp[i - 1] >= pos[i] - x - 1) dp[i] = max(dp[i], pos[i]);
    if (dp[i - 2] >= pos[i] - x - 1 && i > 2)
      dp[i] = max(dp[i], pos[i - 1] + x);
  }
  if (dp[n] >= m - x - 1) return 1;
  dp[2] = max(pos[2], x);
  for (long long i = (3); i <= (n); ++i) {
    dp[i] = dp[i - 1];
    if (dp[i - 1] >= pos[i] - 1) dp[i] = max(dp[i], pos[i] + x);
    if (dp[i - 1] >= pos[i] - x - 1) dp[i] = max(dp[i], pos[i]);
    if (dp[i - 2] >= pos[i] - x - 1) dp[i] = max(dp[i], pos[i - 1] + x);
  }
  if (dp[n] >= min(m - 1, m + pos[2] - x - 1)) return 1;
  return 0;
}
int main() {
  m = read();
  n = read();
  long long now = 1;
  for (long long i = (1); i <= (n); ++i) a[i] = read(), a[i + n] = a[i] + m;
  if (n == 1) {
    return printf("%lld\n", m - 1), 0;
  }
  for (long long i = (2); i <= (n); ++i)
    if (a[now + 1] - a[now] < a[i + 1] - a[i]) now = i;
  long long le = 0, rig = a[now + 1] - a[now] - 1, mid = 0, ans = 0;
  for (long long i = (1); i <= (n); ++i) pos[i] = a[i + now];
  long long cur = pos[1];
  for (long long i = (1); i <= (n); ++i) pos[i] -= cur;
  while (le <= rig) {
    mid = (le + rig) >> 1;
    if (chk(mid))
      ans = mid, rig = mid - 1;
    else
      le = mid + 1;
  }
  return printf("%lld\n", ans), 0;
}
