#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int m, n, a[N], mx = 0, id, dp[N];
inline bool check(int k) {
  memset(dp, 0, sizeof(dp));
  bool flag = 1;
  for (int i = id + 1; i < n + id; ++i) {
    if (a[i] - a[i - 1] - 1 > dp[i - 1] + k) {
      flag = 0;
      break;
    }
    if (a[i] - a[i - 1] - 1 > dp[i - 1])
      dp[i] = 0;
    else
      dp[i] = k;
    if (i > id + 1 && a[i] - a[i - 2] - 1 <= dp[i - 2] + k)
      dp[i] = max(dp[i], a[i - 1] + k - a[i]);
  }
  if (dp[n + id - 1] + k >= a[n + id] - a[n + id - 1] - 1 && flag) return 1;
  flag = 1;
  int s = 0;
  memset(dp, 0, sizeof(dp));
  dp[id] = k;
  dp[id + 1] = max(dp[id + 1], dp[id] + a[id] - a[id + 1]);
  for (int i = id + 2; i < n + id; ++i) {
    if (a[i] - a[i - 1] - 1 > dp[i - 1] + k) {
      flag = 0;
      break;
    }
    if (a[i] - a[i - 1] - 1 > dp[i - 1])
      dp[i] = 0;
    else
      dp[i] = k;
    if (a[i] - a[i - 2] - 1 <= dp[i - 2] + k)
      dp[i] = max(dp[i], a[i - 1] + k - a[i]);
    dp[i] = max(dp[i], dp[i - 1] + a[i - 1] - a[i]);
  }
  if (flag &&
      dp[n + id - 1] + a[id] - a[id + 1] + k >= a[n + id] - a[n + id - 1] - 1)
    return 1;
  return 0;
}
int main() {
  scanf("%d%d", &m, &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i) a[i + n] = a[i] + m;
  for (int i = 1; i < n; ++i)
    if (mx < a[i + 1] - a[i]) mx = a[i + 1] - a[i], id = i + 1;
  if (mx < a[1] + m - a[n]) mx = a[1] + m - a[n], id = 1;
  int l = 0, r = 1e9;
  check(12);
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  printf("%d", r);
  return 0;
}
