#include "gap.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long findGap(int T,int n) {
if (T == 1) {
vector<ll> a(n);
int l = 0, r = n - 1;
ll mn = 0, mx = 1e18;
while (l <= r) {
long long s = mn, t = mx;
MinMax(s, t, &mn, &mx);
if (mn == -1 && mx == -1) break;
a[l++] = mn++, a[r--] = mx--;
}
ll ans = 0;
for (int i = 0; i < n - 1; ++i)
ans = max(ans, a[i + 1] - a[i]);
return ans;
}
vector<ll> a;
ll mx, mn;
MinMax(0, 1e18, &mn, &mx);
ll B = ceil(1.0 * (mx - mn) / (n - 1));
for (ll l = mn, r; l <= mx; l = r + 1) {
r = min(mx, l + B);
ll x, y;
MinMax(l, r, &x, &y);
if (x != -1 || y != -1)
a.push_back(x), a.push_back(y);
}
long long ans = 0;
for (int i = 0; i < (int) a.size() - 1; ++i)
ans = max(ans, a[i + 1] - a[i]);
return ans;
}