#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int v[100005], dp[100005], n, m, aux;
int calc(int nr, int x) {
  dp[0] = 1;
  if (x) dp[x] = max(nr + 1, v[1] + 1);
  int i;
  for (i = max(1, x + 1); i < n; i++) {
    if (dp[i - 1] >= v[i])
      dp[i] = v[i] + nr + 1;
    else if (dp[i - 1] >= v[i] - nr)
      dp[i] = v[i] + 1;
    else
      dp[i] = dp[i - 1];
    if (i > 1 && dp[i - 2] >= v[i] - nr) dp[i] = max(dp[i], v[i - 1] + nr + 1);
  }
  if (dp[n - 1] >= min(m, m + v[x] - nr)) return 1;
  return 0;
}
int main() {
  int i, mini, poz = 0;
  scanf("%d%d", &m, &n);
  for (i = 0; i < n; i++) scanf("%d", &v[i]);
  mini = m - v[n - 1] + v[0];
  for (i = 0; i < n - 1; i++)
    if (v[i + 1] - v[i] > mini) mini = v[i + 1] - v[i], poz = i + 1;
  rotate(v, v + poz, v + n);
  for (i = n - 1; i >= 0; i--) {
    v[i] = v[i] - v[0];
    if (v[i] < 0) v[i] += m;
  }
  int st = 0, dr = m, mij;
  while (st < dr) {
    mij = (st + dr) / 2;
    if (calc(mij, -1) || calc(mij, 0) || calc(mij, 1))
      dr = mij;
    else
      st = mij + 1;
  }
  printf("%d\n", st);
  return 0;
}
