#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 21;
const long long mod = 998244353;
const int Inf = 1e9;
int n, m;
int a[N];
int dp[N][2];
bool check(int x) {
  int st0 = 0, st1 = 0;
  for (; st0 <= x;) {
    dp[0][0] = st0 ? st0 : -x;
    dp[0][1] = st1;
    for (int i = (1); i < (n + 1); ++i) dp[i][0] = Inf, dp[i][1] = 0;
    for (int i = (0); i < (n); ++i) {
      if (dp[i][0] > x) return 0;
      int l1 = a[i + 1] - a[i] + dp[i][0];
      if (l1 > 0 && dp[i][0] <= 0) --l1;
      if (l1 <= 0)
        dp[i + 1][0] = -x;
      else
        dp[i + 1][0] = min(dp[i + 1][0], l1);
      int l2 = a[i + 1] - a[i] + dp[i][1];
      if (l2 > 0) --l2;
      if (l2 <= 0)
        dp[i + 1][0] = -x;
      else
        dp[i + 1][0] = min(dp[i + 1][0], l2);
      if (l1 <= x) dp[i + 1][1] = min(dp[i + 1][1], a[i + 1] - a[i] - x);
      dp[i + 1][1] = min(dp[i + 1][1], l2);
    }
    if (dp[n][0] <= st0 && dp[n][1] <= st1) return 1;
    st0 = dp[n][0], st1 = dp[n][1];
  }
  return 0;
}
int main() {
  scanf("%d%d", &m, &n);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]);
  a[n] = a[0] + m;
  int l = 0, r = m;
  while (l < r) {
    int mid = l + r >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  cout << r;
}
