#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 = 1e5 + 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)
{
if (l > r) 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;
int mid1 = (l * 2 + r) / 3;
int mid2 = (l + r * 2) / 3;
DAC(l, mid1);
DAC(mid1 + 1, mid2);
DAC(mid2 + 1, r);
}
int solve2()
{
DAC(0, oo);
sort(a + 1, a + n + 1);
for (int i = 1; i < n; 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
