#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
int main() {
  int num, n;
  scanf("%d\n", &num);
  scanf("%d\n", &n);
  std::vector<int> a(n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = n - 1; i >= 0; i--) a[i] = a[i] - a[0];
  if (n == num) {
    cout << 0;
    return 0;
  }
  if (n == 1) {
    cout << num - 1;
    return 0;
  }
  if (n == 2) {
    int x = a[1] - a[0];
    int y = num + a[0] - a[1];
    if (x == 1 || y == 1) {
      int gap = x + y - 1;
      cout << gap / 2;
    } else {
      cout << min(max(x, y) - 1, min(x, y) + (max(x, y)) / 2);
    }
    return 0;
  }
  int l = 0;
  int r = num;
  while (r - l > 1) {
    int m = (r + l) / 2;
    int p = 1;
    int reach = m;
    int bonus = 0;
    if (n > 2) {
      if (a[2] <= m + 1) bonus = m - a[1];
    }
    bool f = false;
    while (p < n) {
      if (a[p] <= reach + 1) {
        reach = a[p] + m;
        p++;
      } else {
        int rp = p;
        while (rp < n && a[rp] - reach <= m + 1) rp++;
        rp--;
        if (rp < p) {
          f = false;
          break;
        } else if (rp == p) {
          reach = a[p];
          p++;
        } else if (rp == p + 1) {
          if (a[p + 1] - a[p] == 1) {
            reach = a[p + 1] + m;
            p += 2;
          } else {
            reach = a[p] + m;
            p += 2;
          }
        } else {
          reach = a[rp] + m;
          p = rp + 1;
        }
      }
    }
    if (reach >= num - 1 - bonus) f = true;
    if (f)
      r = m;
    else {
      int reach = m;
      int bonus = m - a[1];
      p = 2;
      while (p < n) {
        if (a[p] <= reach + 1) {
          reach = a[p] + m;
          p++;
        } else {
          int rp = p;
          while (rp < n && a[rp] - reach <= m + 1) rp++;
          rp--;
          if (rp < p) {
            f = false;
            break;
          } else if (rp == p) {
            reach = a[p];
            p++;
          } else if (rp == p + 1) {
            if (a[p + 1] - a[p] == 1) {
              reach = a[p + 1] + m;
              p += 2;
            } else {
              reach = a[p] + m;
              p += 2;
            }
          } else {
            reach = a[rp] + m;
            p = rp + 1;
          }
        }
      }
      if (reach >= num - 1 - bonus) f = true;
      if (f)
        r = m;
      else
        l = m;
    }
  }
  int ans = r;
  std::vector<int> b;
  b.push_back(0);
  for (int i = n - 1; i > 0; i--) b.push_back(num - a[i]);
  a = b;
  l = 0;
  r = num;
  while (r - l > 1) {
    int m = (r + l) / 2;
    int p = 1;
    int reach = m;
    int bonus = 0;
    if (n > 2) {
      if (a[2] <= m + 1) bonus = m - a[1];
    }
    bool f = false;
    while (p < n) {
      if (a[p] <= reach + 1) {
        reach = a[p] + m;
        p++;
      } else {
        int rp = p;
        while (rp < n && a[rp] - reach <= m + 1) rp++;
        rp--;
        if (rp < p) {
          f = false;
          break;
        } else if (rp == p) {
          reach = a[p];
          p++;
        } else if (rp == p + 1) {
          if (a[p + 1] - a[p] == 1) {
            reach = a[p + 1] + m;
            p += 2;
          } else {
            reach = a[p] + m;
            p += 2;
          }
        } else {
          reach = a[rp] + m;
          p = rp + 1;
        }
      }
    }
    if (reach >= num - 1 - bonus) f = true;
    if (f)
      r = m;
    else {
      int reach = m;
      int bonus = m - a[1];
      p = 2;
      while (p < n) {
        if (a[p] <= reach + 1) {
          reach = a[p] + m;
          p++;
        } else {
          int rp = p;
          while (rp < n && a[rp] - reach <= m + 1) rp++;
          rp--;
          if (rp < p) {
            f = false;
            break;
          } else if (rp == p) {
            reach = a[p];
            p++;
          } else if (rp == p + 1) {
            if (a[p + 1] - a[p] == 1) {
              reach = a[p + 1] + m;
              p += 2;
            } else {
              reach = a[p] + m;
              p += 2;
            }
          } else {
            reach = a[rp] + m;
            p = rp + 1;
          }
        }
      }
      if (reach >= num - 1 - bonus) f = true;
      if (f)
        r = m;
      else
        l = m;
    }
  }
  ans = min(ans, r);
  cout << ans;
}
