#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  int L, n;
  cin >> L >> n;
  if (n == 1) {
    cout << L - 1 << endl;
    return 0;
  }
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  sort(a.begin(), a.end());
  int max_i = 1;
  for (int i = 2; i < n; ++i)
    if (a[i] - a[i - 1] > a[max_i] - a[max_i - 1]) max_i = i;
  if (a[0] + L - a[n - 1] > a[max_i] - a[max_i - 1]) max_i = 0;
  rotate(a.begin(), a.begin() + max_i, a.end());
  for (int i = n - 1; ~i; --i) a[i] = (a[i] - a[0] + L) % L;
  int l = (a[0] + L - a[n - 1]) >> 1, r = a[0] + L - a[n - 1] - 2;
  while (l <= r) {
    int mid = l + r >> 1;
    auto check1 = [&]() {
      vector<pair<int, int> > dp, pd;
      dp.push_back(make_pair(a[0], a[0]));
      for (int i = 1; i < n; ++i) {
        pd.clear();
        for (auto &t : dp) {
          int cov = t.first, mx = t.second;
          if (a[i] - mid > cov + 1) continue;
          pd.push_back(make_pair(max(mx, a[i]), max(mx, a[i])));
          if (cov >= a[i] - 1)
            pd.push_back(make_pair(a[i] + mid, a[i] + mid));
          else
            pd.push_back(make_pair(cov, a[i] + mid));
        }
        sort(pd.begin(), pd.end(), [&](pair<int, int> a, pair<int, int> b) {
          return a.first != b.first ? a.first > b.first : a.second > b.second;
        });
        dp.clear();
        int mx = -1;
        for (auto &t : pd)
          if (t.second > mx) dp.push_back(t), mx = t.second;
        if (!dp.size()) return false;
      }
      for (auto &t : dp)
        if (t.first >= a[0] - mid + L - 1) return true;
      return false;
    };
    auto check2 = [&]() {
      vector<pair<int, int> > dp, pd;
      dp.push_back(make_pair(a[0] + mid, a[0] + mid));
      for (int i = 2; i < n; ++i) {
        pd.clear();
        for (auto &t : dp) {
          int cov = t.first, mx = t.second;
          if (a[i] - mid > cov + 1) continue;
          pd.push_back(make_pair(max(mx, a[i]), max(mx, a[i])));
          if (cov >= a[i] - 1)
            pd.push_back(make_pair(a[i] + mid, a[i] + mid));
          else
            pd.push_back(make_pair(cov, a[i] + mid));
        }
        sort(pd.begin(), pd.end(), [&](pair<int, int> a, pair<int, int> b) {
          return a.first != b.first ? a.first > b.first : a.second > b.second;
        });
        dp.clear();
        int mx = -1;
        for (auto &t : pd)
          if (t.second > mx) dp.push_back(t), mx = t.second;
        if (!dp.size()) return false;
      }
      for (auto &t : dp)
        if (t.first >= a[1] - mid + L - 1) return true;
      return false;
    };
    if (check1() || check2())
      r = mid - 1;
    else
      l = mid + 1;
  }
  cout << l << endl;
  return 0;
}
