#include <bits/stdc++.h>
using namespace std;
int n, m, Maxt, Max;
int a[100001], b[100001], cnt;
int f[100001];
bool check(int T) {
  int flag;
  for (int i = 1; i <= n; ++i) f[i] = 0;
  f[1] = b[1];
  flag = 1;
  for (int i = 2; i <= n; ++i) {
    if (f[i - 1] < b[i] - T - 1) {
      flag = 0;
      break;
    }
    f[i] = b[i];
    if (f[i - 1] >= b[i] - 1) f[i] = b[i] + T;
    if (i - 2 > 0) {
      if (f[i - 2] >= b[i] - T - 1) f[i] = max(f[i], b[i - 1] + T);
    }
  }
  if (flag && f[n] >= b[1] + m - T - 1) return 1;
  if (b[1] + T >= b[2] - 1) {
    for (int i = 1; i <= n; ++i) f[i] = 0;
    f[2] = max(b[1] + T, b[2]);
    flag = 1;
    for (int i = 3; i <= n; ++i) {
      if (f[i - 1] < b[i] - T - 1) {
        flag = 0;
        break;
      }
      f[i] = b[i];
      if (f[i - 1] + 1 >= b[i]) f[i] = b[i] + T;
      if (i - 2 > 0) {
        if (f[i - 2] >= b[i] - T - 1) f[i] = max(f[i], b[i - 1] + T);
      }
    }
    if (flag && f[n] >= b[2] + m - T - 1) return 1;
  }
  return 0;
}
int main() {
  scanf("%d%d", &m, &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    a[i]--;
  }
  if (n == 1) {
    printf("%d\n", m - 1);
    return 0;
  }
  for (int i = 1; i <= n; ++i) {
    int j = i == n ? 1 : i + 1;
    int tmp = (a[j] + m - a[i]) % m;
    if (tmp > Max) Max = tmp, Maxt = i;
  }
  int now = Maxt % n + 1;
  for (int i = 1; i <= n; ++i) {
    b[i] = a[now];
    now = now % n + 1;
  }
  for (int i = 2; i <= n; ++i)
    if (b[i] < b[i - 1]) b[i] += m;
  for (int i = n; i; --i) b[i] -= b[1];
  int l, r;
  l = 0;
  r = Max - 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid))
      r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%d\n", l);
  return 0;
}
