#include<bits/stdc++.h>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
#define rep(i, f, t) for(int i = f; i <= t; i ++)
#define urep(i, f, t) for(int i = f; i >= t; i --)
#define pb push_back
#define pq priority_queue
#define addr(v) v.begin(), v.end()
#define qstream std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
const ll INF = 1e18 + 7;

ll gcd(ll a, ll b) {
	return (b == 0) ? a : gcd(b, a % b);
}

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> v, interal;
	
	rep(i, 1, k) {
		int tmp;
		cin >> tmp;
		v.pb(tmp);
	}
	sort(addr(v));
	if((v.size() && *v.begin() > 1))interal.pb(*v.begin() - 1);
	rep(i, 1, (int)v.size() - 1) {
		if(v[i] - v[i - 1] - 1) interal.pb(v[i] - v[i - 1] - 1);
	}
	if(v.size() && n - *v.rbegin() > 1) interal.pb(n - *v.rbegin());
	ll cnt = 0, ans;
//	if(v.size()) {
//		ans = *interal.begin();
//		cout << ans << endl;
//		rep(i, 1, (int)interal.size() - 1) {
//			ans = gcd(ans, interal[i]);
//			cout << interal[i] << " " << ans << endl;
//		}
//		rep(i, 0, (int)interal.size() - 1) {
//			cnt += interal[i] / ans;
//		}
//	}
//	//cout << ans << endl;
	if(interal.size()) {
		sort(addr(interal));
		ans = *interal.begin();
		rep(i, 0, (int)interal.size() - 1) {
			cnt += (interal[i] % ans) ? interal[i] / ans + 1 : interal[i] / ans;
		}
	}
	if(!k) cnt = 1;
	cout << cnt << endl;
	return 0;
}
#line 1 "main.cpp"
#include <bits/stdc++.h>
using namespace std;

// template {{{
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

#define  range(i, l, r) for (i64 i = (i64)(l); i < (i64)(r); (i) += 1)
#define rrange(i, l, r) for (i64 i = (i64)(r) - 1; i >= (i64)(l); (i) -= 1)

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

constexpr i32 dx[] = {0, -1, 1, 0, -1, 1, -1, 1}; 
constexpr i32 dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};

struct IoSetup { IoSetup(i32 x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != (int)v.size() ? " " : ""); } return os; } 
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// }}}

void solve() {
  int n = input();

  vector< pair<pair<int, int>, int>> vs;
  vector< pair<int, int> > ps;
  range(i, 0, n) {
    pair<int, int> p;
    cin >> p;
    ps.emplace_back(p);
    vs.emplace_back(p, i);
  }

  vector< int > idxs;
  whole(sort, vs);
  idxs.emplace_back(vs[0].second);
  idxs.emplace_back(vs[1].second);
  idxs.emplace_back(vs[n-1].second);
  idxs.emplace_back(vs[n-2].second);

  whole(sort, vs, [](auto &a, auto &b) { return a.first.second < b.first.second; });
  idxs.emplace_back(vs[0].second);
  idxs.emplace_back(vs[1].second);
  idxs.emplace_back(vs[n-1].second);
  idxs.emplace_back(vs[n-2].second);

  whole(sort, idxs);
  idxs.erase(whole(unique, idxs), idxs.end());

  vector< i64 > ds; 
  for (auto &i : idxs) for (auto &j : idxs) {
    if (i >= j) continue;
    i64 d = max(abs(ps[i].first - ps[j].first), abs(ps[i].second - ps[j].second));
    ds.emplace_back(d);
  }

  rwhole(sort, ds);
  cout << ds[1] << endl;
}

signed main() {
  solve();
}
