#include <bits/stdc++.h>
using namespace std;
const int MXN = 100005;
const int INF = 1029384756;
int N, M, A[MXN], dp[MXN][2];
void calc(int st, int step) {
  for (int i = (st); i <= (N - 1); i++) {
    dp[i][0] = 0;
    int x;
    x = dp[i - 1][0];
    if (x >= A[i] - step) x = max(x, A[i] + 1);
    dp[i][0] = max(dp[i][0], x);
    x = dp[i - 1][1];
    if (x >= A[i] - step) x = max(A[i], A[i - 1] + step) + 1;
    dp[i][0] = max(dp[i][0], x);
    dp[i][1] = 0;
    x = max(dp[i - 1][0], dp[i - 1][1]);
    if (x >= A[i]) x = A[i] + step + 1;
    dp[i][1] = max(dp[i][1], x);
  }
}
bool check(int step) {
  dp[0][0] = dp[0][1] = -INF;
  dp[0][0] = A[0] + 1;
  calc(1, step);
  if (max(dp[N - 1][0], dp[N - 1][1]) >= A[0] - step + M) return true;
  if (A[0] + step + 1 < A[1] - step) return false;
  dp[1][0] = dp[1][1] = -INF;
  dp[1][0] = max(A[0] + step, A[1]) + 1;
  calc(2, step);
  if (max(dp[N - 1][0], dp[N - 1][1]) >= min(A[0], A[1] - step) + M)
    return true;
  return false;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  cin >> M;
  cin >> N;
  for (int i = 0; i < (N); i++) {
    cin >> A[i];
    A[i] %= M;
  }
  if (N == 1) {
    cout << M - 1 << endl;
    return 0;
  }
  sort(A, A + N);
  int bv = 0;
  int bc = A[0] + M - A[N - 1];
  for (int i = (1); i <= (N - 1); i++) {
    if (A[i] - A[i - 1] > bc) {
      bv = i;
      bc = A[i] - A[i - 1];
    }
  }
  rotate(A, A + bv, A + N);
  A[N] = A[0] + M;
  for (int i = (1); i <= (N - 1); i++) {
    if (A[i] < A[i - 1]) A[i] += M;
  }
  int l = 0, r = bc;
  while (l < r) {
    int m = (l + r) / 2;
    if (check(m))
      r = m;
    else
      l = m + 1;
  }
  cout << l << endl;
  return 0;
}
