#include <bits/stdc++.h>
using namespace std;
long long m, n, l[123456];
vector<long long> v;
bool solve(long long cur, long long pos, long long meme, long long k) {
  if (cur == n) {
    if (pos >= meme)
      return true;
    else
      return false;
  }
  l[cur] = pos;
  long long x = v[cur];
  if (pos < x) {
    if (x - pos > k) return false;
    if (x - k <= l[cur - 1]) {
      return solve(cur + 1, max(v[cur - 1] + k, x) + 1, meme, k);
    }
    return solve(cur + 1, x + 1, meme, k);
  }
  return solve(cur + 1, x + k + 1, meme, k);
}
int main() {
  cin >> m;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    v.push_back(x - 1);
  }
  if (n == 1) {
    cout << m - 1 << endl;
    return 0;
  }
  sort(v.begin(), v.end());
  v.push_back(v.front() + m);
  int mx = -1, mxe = -1;
  for (int i = 1; i <= n; ++i) {
    if (v[i] - v[i - 1] > mx) mx = v[i] - v[i - 1], mxe = v[i];
  }
  v.pop_back();
  for (int i = 0; i < n; ++i) v[i] = (v[i] - mxe + m) % m;
  sort(v.begin(), v.end());
  long long res = m - 1, esq = 0, dir = m - 1;
  l[0] = -1e9;
  while (esq <= dir) {
    long long mid = (esq + dir) / 2;
    int flag = 0;
    flag = solve(1, v[0] + mid + 1, v[0] + m, mid);
    flag |= solve(1, v[0] + 1, v[0] - mid + m, mid);
    if (v[1] - mid < v[0]) {
      l[1] = v[1] - mid;
      flag |= solve(2, v[0] + mid + 1, v[1] - mid + m, mid);
    }
    if (flag) {
      dir = mid - 1;
      res = min(res, mid);
    } else
      esq = mid + 1;
  }
  cout << res << endl;
  return 0;
}
