#include <bits/stdc++.h>
using namespace std;
int dp[111111][2], num[111111], tmp[111111], n, m;
bool solve(int x, int stx, int edx, int nows) {
  dp[1][nows] = stx, dp[1][!nows] = -1e9 - 7;
  if (nows && n > 1) {
    if (num[2] >= x) return 0;
    dp[2][1] = -1e9 - 7, dp[2][0] = stx;
    edx = m + num[2] - x + 1;
    if (dp[2][0] >= edx - 1 || dp[2][1] >= edx - 1) return 1;
  }
  for (int i = nows + 2; i <= n; i++) {
    dp[i][1] = dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
    if (num[i] - dp[i - 1][0] <= x) dp[i][0] = max(dp[i - 1][0], num[i]);
    if (num[i] - dp[i - 1][1] <= x) dp[i][0] = max(num[i], num[i - 1] + x - 1);
    if (dp[i - 1][1] >= num[i] - 1 || dp[i - 1][0] >= num[i] - 1)
      dp[i][1] = num[i] + x - 1;
    if (dp[i][0] >= edx - 1 || dp[i][1] >= edx - 1) return 1;
  }
  return 0;
}
int main(void) {
  int maxnum = 0, maxpos = 0;
  scanf("%d%d", &m, &n);
  for (int i = 1; i <= n; i++) scanf("%d", &tmp[i]);
  tmp[n + 1] = tmp[1] + m;
  for (int i = 2; i <= n + 1; i++)
    if (maxnum < tmp[i] - tmp[i - 1]) maxnum = tmp[i] - tmp[i - 1], maxpos = i;
  for (int i = 1; i <= n; i++) {
    int k = (maxpos + i - 2) % n + 1;
    if (tmp[k] < tmp[maxpos])
      num[i] = m - (tmp[maxpos] - tmp[k]) + 1;
    else
      num[i] = tmp[k] - tmp[maxpos] + 1;
  }
  int l = 1, r = maxnum - 1, res = maxnum;
  while (l <= r) {
    int mid = (l + r) / 2;
    int k = solve(mid, mid, m + 1, 1) | solve(mid, 1, m + 1 - mid + 1, 0);
    if (k)
      res = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%d\n", res - 1);
}
