#include <bits/stdc++.h>
using namespace std;
static void my_assert(int k){ if (!k) exit(1); }
using ll = long long;
static int subtask_num, N;
static long long A[100001];
static long long call_count;
void MinMax(long long s, long long t, long long *mn, long long *mx)
{
int lo = 1, hi = N, left = N+1, right = 0;
my_assert(s <= t && mn != NULL && mx != NULL);
while (lo <= hi){
int mid = (lo+hi)>>1;
if (A[mid] >= s) hi = mid - 1, left = mid;
else lo = mid + 1;
}
lo = 1, hi = N;
while (lo <= hi){
int mid = (lo+hi)>>1;
if (A[mid] <= t) lo = mid + 1, right = mid;
else hi = mid - 1;
}
if (left > right) *mn = *mx = -1;
else{
*mn = A[left];
*mx = A[right];
}
if (subtask_num == 1) call_count++;
else if (subtask_num == 2) call_count += right-left+2;
}
long long findGap(int T, int N) {
if (T == 1 || N <= 9) {
ll lf = -1, rg = 1000000000000000000 + 1, bs = 0;
for (int j = 0; j < (N + 1) / 2; j++) {
ll mn, mx;
ll *uk_mn{&mn}, *uk_mx{&mx};
MinMax(lf + 1, rg - 1, uk_mn, uk_mx);
if (lf != -1) bs = max(bs, mn - lf);
if (rg != 1000000000000000000 + 1) bs = max(bs, rg - mx);
if (N % 2 == 0 && j + 1 == N / 2) bs = max(bs, mx - mn);
lf = mn; rg = mx;
}
return bs;
}
ll mn, mx;
ll *uk_mn{&mn}, *uk_mx{&mx};
const ll MAXC = 1000000000000000000;
MinMax(0, MAXC, uk_mn, uk_mx);
ll M = mx;
ll elem = mn, ans = 0;
while (elem < M) {
if (ans != 0) {
MinMax(elem + 1, elem + ans, uk_mn, uk_mx);
if (mx != -1) {
elem = mx; continue;
}
}
ll cg = ans + 1;
while (true) {
MinMax(elem + cg, elem + 2 * cg, uk_mn, uk_mx);
if (mx != -1) {
ans = mn - elem;
elem = mx;
break;
}
cg = 2 * cg + 1;
}
}
return ans;
}
int main()
{
FILE *in = stdin, *out = stdout;
my_assert(2 == fscanf(in, "%d%d", &subtask_num, &N));
my_assert(1 <= subtask_num && subtask_num <= 2);
my_assert(2 <= N && N <= 100000);
for (int i=1;i<=N;i++) my_assert(1 == fscanf(in, "%lld", A+i));
for (int i=1;i<N;i++) my_assert(A[i] < A[i+1]);
fprintf(out, "%lld\n", findGap(subtask_num, N));
fprintf(out, "%lld\n", call_count);
}