#include <bits/stdc++.h>
using namespace std;
const int MAXN = (1e5 + 5) * 2;
void Max(int &x, int y) {
  if (x < y) x = y;
}
int n, m;
int a[MAXN];
int dp[MAXN];
bool chk1(int s, int x) {
  memset(dp, 0, sizeof(dp));
  for (int i = s, iend = s + n - 1; i <= iend; ++i) {
    int d = a[i + 1] - a[i] - 1;
    if (dp[i] + x < d) return false;
    if (dp[i] >= d) Max(dp[i + 1], x);
    if (dp[i] + x >= a[i + 2] - a[i] - 1)
      Max(dp[i + 2], x - (a[i + 2] - a[i + 1]));
  }
  int t = s + n - 1, d = a[s] - a[s - 1] - 1;
  if (dp[t] + x < d)
    return false;
  else
    return true;
}
bool chk2(int s, int x) {
  memset(dp, 0, sizeof(dp));
  if (x < a[s + 1] - a[s] - 1) return false;
  Max(dp[s + 1], x - (a[s + 1] - a[s]));
  for (int i = s + 1, iend = s + n - 1; i <= iend; ++i) {
    int d = a[i + 1] - a[i] - 1;
    if (dp[i] + x < d) return false;
    if (dp[i] >= d) Max(dp[i + 1], x);
    if (dp[i] + x >= a[i + 2] - a[i] - 1)
      Max(dp[i + 2], x - (a[i + 2] - a[i + 1]));
  }
  int t = s + n - 1, d = a[s + 1] - a[s - 1] - 1;
  if (dp[t] + x < d)
    return false;
  else
    return true;
}
bool check(int x) {
  int s = -1;
  for (int i = 1, iend = n; i <= iend; ++i) {
    if (a[i + 1] - a[i] > x + 1) s = i + 1;
  }
  if (s == -1)
    return true;
  else
    return chk1(s, x) || chk2(s, x);
}
int main() {
  cin >> m >> n;
  for (int i = 1, iend = n; i <= iend; ++i) scanf("%d", &a[i]);
  for (int i = 1, iend = n; i <= iend; ++i) a[i + n] = m + a[i];
  if (n == 1) {
    cout << m - 1 << endl;
    return 0;
  }
  int l = 0, r = m, res;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid))
      res = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  cout << res << endl;
  return 0;
}
