/* cerberus97 - Hanit Banga */
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#ifndef LOCAL
#include "gap.h"
#endif
using namespace std;
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const ll INF = 1e18;
ll findGap(int T, int N);
ll findGap_small(int N);
void query(ll s, ll t, ll &mn, ll &mx, int T);
int M;
set<pll> S;
#ifdef LOCAL
int main() {
int T, n; cin >> T >> n;
vector<ll> v(n);
for (int i = 1; i <= n; ++i) {
cin >> v[i - 1];
}
sort(v.begin(), v.end());
for (int i = 0; i < n; ++i) {
S.insert({v[i], i});
}
S.insert({-1, -1});
S.insert({INF + 1, n});
cout << findGap(T, n) << endl << M << ' ';
if (T == 1) {
cout << (n + 1) / 2 << endl;
} else {
cout << 3 * n << endl;
}
}
#endif
ll findGap(int T, int N) {
if (T == 1) {
return findGap_small(N);
}
ll mn, mx;
query(0, INF, mn, mx, T);
if (N <= 2) {
return mx - mn;
}
ll A = mn, B = mx, best = (B - A + N - 2) / (N - 1), sz = best + 1;
while (A < B) {
if (A + sz >= B) {
query(A + 1, B - 1, mn, mx, T);
mx = B;
if (mn == -1) {
mn = B;
}
} else {
query(A + 1, A + sz, mn, mx, T);
}
if (mn == -1) {
sz *= 2;
continue;
}
best = max(best, mn - A);
sz = best + 1;
A = mx;
}
return best;
}
ll findGap_small(int N) {
ll mn, mx;
query(0, INF, mn, mx, 1);
ll best = 0;
ll A = mn, B = mx;
N -= 2;
while (A < B and N > 0) {
query(A + 1, B - 1, mn, mx, 1);
if (mn == -1) {
best = max(best, B - A);
break;
} else {
best = max(best, mn - A);
best = max(best, B - mx);
A = mn; B = mx;
N -= 2;
}
}
return max(best, B - A);
}
void query(ll s, ll t, ll &mn, ll &mx, int T) {
if (s > t) {
mn = mx = -1;
return;
}
#ifdef LOCAL
assert(s <= t);
++M;
auto l = S.lower_bound({s, -INF});
auto r = S.upper_bound({t, INF + 10});
--r;
if (l->second <= r->second) {
mn = l->first;
mx = r->first;
if (T == 2) {
M += (r->second - l->second + 1);
}
} else {
mn = mx = -1;
}
#else
MinMax(s, t, &mn, &mx);
#endif
}
