#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], n, m, b[N], dp[N];
int mxdis, pos;
bool check(int x) {
  if (x >= mxdis - 1) return 1;
  memset(dp, 0, sizeof(dp));
  dp[1] = 1;
  bool fg = 1;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1];
    if (dp[i - 1] >= b[i] - 1)
      dp[i] = b[i] + x;
    else if (dp[i - 1] >= b[i] - x - 1)
      dp[i] = b[i];
    else {
      fg = 0;
      break;
    }
    if (i >= 3 && b[i] - x <= dp[i - 2] + 1) dp[i] = max(dp[i], b[i - 1] + x);
  }
  if (fg && dp[n] >= m - x) return 1;
  fg = 1;
  memset(dp, 0, sizeof(dp));
  dp[2] = max(x + 1, b[2]);
  for (int i = 3; i <= n; i++) {
    if (dp[i - 1] >= b[i] - 1)
      dp[i] = b[i] + x;
    else if (dp[i - 1] >= b[i] - x - 1)
      dp[i] = b[i];
    else {
      fg = 0;
      break;
    }
    if (i >= 4 && b[i] - x <= dp[i - 2] + 1) dp[i] = max(dp[i], b[i - 1] + x);
  }
  if (fg && dp[n] >= min(m, m + b[2] - x - 1)) return 1;
  return 0;
}
int main() {
  scanf("%d%d", &m, &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++) {
    int ds = (i == 1) ? (m - a[n] + a[1]) : (a[i] - a[i - 1]);
    if (ds > mxdis) mxdis = ds, pos = i;
  }
  for (int i = 1, j = pos; i <= n; i++, j = j % n + 1) {
    b[i] = a[j] - a[pos] + 1;
    if (b[i] < 0) b[i] += m;
  }
  int L = mxdis / 2, R = mxdis - 1, B, M;
  while (L <= R) {
    M = (L + R) >> 1;
    if (check(M))
      B = M, R = M - 1;
    else
      L = M + 1;
  }
  cout << B << endl;
}
