#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  long long L;
  int n;
  cin >> L >> n;
  vector<long long> x(n);
  for (int i = 0; i < n; ++i) cin >> x[i];
  sort(x.begin(), x.end());
  for (int i = 1; i < n; ++i) x[i] -= x[0];
  x[0] = 0;
  int rem = 0;
  long long mx = L - x.back();
  for (int i = 0; i < n - 1; ++i)
    if (x[i + 1] - x[i] > mx) mx = x[i + 1] - x[i], rem = i + 1;
  rotate(x.begin(), x.begin() + rem, x.end());
  for (int i = 1; i < n; ++i) x[i] = (x[i] - x[0] + L) % L;
  x[0] = 0;
  long long lb = 0, rb = L;
  while (lb <= rb) {
    auto mid = lb + rb >> 1;
    auto check = [&](const long long &l, const int &beg) {
      vector<long long> dp(n);
      dp[0] = 1;
      if (beg == 1) dp[1] = max(l + 1, x[1] + 1);
      for (int i = max(1, beg + 1); i < n; ++i) {
        if (dp[i - 1] >= x[i])
          dp[i] = x[i] + l + 1;
        else if (dp[i - 1] >= x[i] - l)
          dp[i] = x[i] + 1;
        else
          dp[i] = dp[i - 1];
        if (i > 1 && dp[i - 2] >= x[i] - l)
          dp[i] = max(dp[i], x[i - 1] + l + 1);
      }
      return dp.back() >= min(L, L + x[(n + beg) % n] - l);
    };
    if (check(mid, -1) || check(mid, 0) || check(mid, 1))
      rb = mid - 1;
    else
      lb = mid + 1;
  }
  cout << lb << endl;
  return 0;
}
