#include <bits/stdc++.h>
using namespace std;
int f[100005][2], a[100005], n, m, b[100005];
bool chk(int x) {
  int st0 = 0, st1 = 0, T = 2;
  while (T--) {
    if (!st0)
      f[0][0] = -x;
    else
      f[0][0] = st0;
    f[0][1] = st1;
    for (int i = 1; i <= n; i++) f[i][0] = 1e9, f[i][1] = 0;
    for (int i = 0; i < n; i++) {
      if (f[i][0] > x) return 0;
      int k1;
      if (f[i][0] > 0)
        k1 = abs(a[i + 1] - a[i]) + f[i][0];
      else {
        k1 = abs(a[i + 1] - a[i]) - x;
        if (k1 > 0) k1--;
      }
      if (k1 < 0)
        f[i + 1][0] = -x;
      else
        f[i + 1][0] = min(f[i + 1][0], k1);
      int k2 = abs(a[i + 1] - a[i]) + f[i][1];
      if (k2 > 0) k2--;
      if (k2 < 0)
        f[i + 1][0] = -x;
      else
        f[i + 1][0] = min(f[i + 1][0], k2);
      if (k1 <= x) f[i + 1][1] = min(f[i + 1][1], abs(a[i + 1] - a[i]) - x);
      f[i + 1][1] = min(f[i + 1][1], k2);
    }
    if (f[n][0] <= st0 && f[n][1] <= st1) return 1;
    st0 = f[n][0];
    st1 = f[n][1];
  }
  return 0;
}
int main() {
  scanf("%d%d", &m, &n);
  int mx = -1e9, mxpos;
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  if (a[0] + m - a[n - 1] > mx) mx = a[0] - a[n - 1] + m, mxpos = n - 1;
  for (int i = 1; i < n; i++)
    if (a[i] - a[i - 1] > mx) {
      mx = a[i] - a[i - 1];
      mxpos = i - 1;
    }
  for (int i = mxpos; i < n; i++) b[i - mxpos] = a[i];
  for (int i = 0; i < mxpos; i++) b[i + n - mxpos] = a[i] + m;
  memcpy(a, b, sizeof(b));
  a[n] = a[0] + m;
  int l = 0, r = m - n, ans = 0;
  while (l <= r) {
    int mid = (l + r) / 2;
    bool flag1 = chk(mid);
    if (flag1)
      r = mid - 1, ans = mid;
    else
      l = mid + 1;
  }
  printf("%d", ans);
}
