#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;
int solve2()
{
MinMax(0, oo, tmpn, tmpx);
a[++cnt] = *tmpn;
a[++cnt] = *tmpx;
int step = (*tmpx - *tmpn + n) / (n - 1);
for (int i = 1, cur = *tmpn; i < n; i++) {
// cout << i << endl;
MinMax(cur + 1, cur + step, tmpn, tmpx);
cur += step;
if (*tmpn == -1) continue;
a[++cnt] = *tmpn;
if (*tmpn != *tmpx) a[++cnt] = *tmpx;
}
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
