#include <bits/stdc++.h>   using namespace std;   const int MAXN = 100000;   const int INF = 0x3f3f3f3f;   int dis[MAXN + 10], pos[MAXN + 10], f[MAXN + 10], Max, m, n;   bool check(const int& x) {     if (x >= dis[1] - 1) return true;     if (2 * x < dis[1] - 1) return false;     f[1] = 0;     for (int i = 2; i <= n; i++) {       f[i] = -INF;       if (f[i - 1] >= pos[i] - 1) f[i] = pos[i] + x;       if (f[i - 1] >= pos[i] - 1 - x) f[i] = max(f[i], pos[i]);       if (i > 2 && f[i - 2] >= pos[i] - 1 - x) f[i] = max(pos[i - 1] + x, f[i]);     }     if (f[n] + x >= m - 1) return true;     f[1] = x, f[2] = max(x, pos[2]);     for (int i = 3; i <= n; i++) {       f[i] = -INF;       if (f[i - 1] >= pos[i] - 1) f[i] = pos[i] + x;       if (f[i - 1] >= pos[i] - 1 - x) f[i] = max(f[i], pos[i]);       if (f[i - 2] >= pos[i] - 1 - x) f[i] = max(pos[i - 1] + x, f[i]);     }     if (f[n] >= min(m - 1, pos[2] + m - 1 - x)) return true;     return false;   }   int tmp[MAXN + 10];   void _rotate(int* arr, int mid, int len) {     int cnt = 0;     for (int i = mid; i <= len; i++) tmp[++cnt] = arr[i];     for (int i = 1; i < mid; i++) tmp[++cnt] = arr[i];     for (int i = 1; i <= len; i++) arr[i] = tmp[i];   }   int main() {     scanf( %d%d , &m, &n);     if (n == 1) {       printf( %d n , m - 1);       return 0;     }     for (int i = 1; i <= n; i++) scanf( %d , &pos[i]);     sort(pos + 1, pos + 1 + n);     pos[0] = pos[n];     int p;     for (int i = 1; i <= n; i++) {       dis[i] = (pos[i] - pos[i - 1] + m) % m;       if (dis[i] > Max) p = i;       Max = max(Max, dis[i]);     }     _rotate(pos, p, n);     _rotate(dis, p, n);     int eff = pos[1];     for (int i = 1; i <= n; i++) pos[i] = (pos[i] - eff + m) % m;     int L = 1, R = Max - 1, ans = 0;     while (L <= R) {       int mid = (L + R) >> 1;       if (check(mid)) {         ans = mid;         R = mid - 1;       } else         L = mid + 1;     }     printf( %d n , ans);     return 0;   }   