#include <bits/stdc++.h>
using namespace std;
bool can_solve(vector<int> owls, int steps, int first, int begin, int end) {
  vector<int> secures(owls.size(), -1023456789);
  secures[first - 1] = begin;
  for (int i = first; i < owls.size(); i++) {
    secures[i] = secures[i - 1];
    if (secures[i - 1] >= owls[i])
      secures[i] = max(secures[i], owls[i] + steps + 1);
    if (i >= 2) {
      if (secures[i - 2] >= owls[i] - steps)
        secures[i] = max(secures[i], owls[i - 1] + steps + 1);
    }
    if (secures[i - 1] >= owls[i] - steps)
      secures[i] = max(secures[i], owls[i] + 1);
  }
  return secures.back() >= end;
}
int main() {
  int m, n;
  scanf("%d %d", &m, &n);
  vector<int> owl(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &owl[i]);
    owl[i] = owl[i] % m;
  }
  if (n == 1) {
    printf("%d\n", m - 1);
    return 0;
  }
  pair<int, int> maxgap(0, -1);
  for (int i = 0; i < n; i++) {
    maxgap = max(maxgap, pair<int, int>((owl[(i + 1) % n] - owl[i] + m) % m - 1,
                                        (i + 1) % n));
  }
  vector<int> nowl;
  for (int i = 0; i < n; i++) {
    nowl.push_back((owl[(i + maxgap.second) % n] - owl[maxgap.second] + m) % m);
  }
  int hi = maxgap.first, lo = (maxgap.first - 1) / 2;
  while (hi - lo > 1) {
    int mid = (hi + lo) / 2;
    if (can_solve(nowl, mid, 1, 1, m - mid))
      hi = mid;
    else {
      if (nowl.size() > 1) {
        if (can_solve(nowl, mid, 2, mid + 1, m + nowl[1] - mid))
          hi = mid;
        else
          lo = mid;
      } else
        lo = mid;
    }
  }
  printf("%d\n", hi);
  return 0;
}
