#include <bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>
inline bool maxi(T &x, const T &val)
{
if (x < val) return x = val, true;
return false;
}
template<typename T>
inline bool mini(T &x, const T &val)
{
if (x > val) return x = val, true;
return false;
}
const int maxn = 3e5 + 10, oo = 1e18;
int n;
int a[maxn];
int res;
void MinMax(long long s, long long t, long long *mn, long long *mx);
int solve1()
{
int st = 0, en = oo;
int *tmpn = new int(0), *tmpx = new int(oo);
int curst = 1, curen = n;
while (curst <= curen) {
MinMax(st, en, tmpn, tmpx);
a[curst++] = *tmpn;
st = *tmpn + 1;
a[curen--] = *tmpx;
en = *tmpx - 1;
}
for (int i = 1; i < n; i++) {
maxi(res, a[i + 1] - a[i]);
}
return res;
}
int *tmpn = new int(0), *tmpx = new int(0);
int cnt = 0;
void DAC(int l, int r)
{
// cout << l << ' ' << r << endl;
if (l > r) return;
if (cnt == n) return;
MinMax(l, r, tmpn, tmpx);
if (*tmpn == -1) return;
a[++cnt] = *tmpn;
if (*tmpn == *tmpx) return;
a[++cnt] = *tmpx;
l = *tmpn + 1;
r = *tmpx - 1;
if (r - l <= (a[2] - a[1]) / max(1ll, (n - 2))) {
while (l <= r) {
MinMax(l, r, tmpn, tmpx);
if (*tmpn == -1) return;
a[++cnt] = *tmpn;
if (*tmpn == *tmpx) break;
a[++cnt] = *tmpx;
l = *tmpn + 1;
r = *tmpx - 1;
}
return;
}
int k = (long double) (r - l + 1) / (a[2] - a[1] + 1) * n + 2;
for (int i = 1, pre = l; pre <= r; i++) {
int tmp = ((long double) l * (k - i) + (long double) r * i) / k;
DAC(pre, tmp);
pre = tmp + 1;
}
}
int solve2()
{
DAC(0, oo);
sort(a + 1, a + cnt + 1);
for (int i = 1; i < cnt; i++) {
maxi(res, a[i + 1] - a[i]);
}
return res;
}
int findGap(signed sub, signed n)
{
::n = n;
if (sub == 1) return solve1();
else return solve2();
}
#undef int
