#include "gap.h"
#include "bits/stdc++.h"
using namespace std;
#define lnl long long
lnl n, ans, k, mn, mx, l, r, inf = 1e18;
lnl findGap(int T, int N) {
MinMax(0, LLONG_MAX, &l, &r);
if (T == 1) {
N = (N - 1) / 2;
while (N--) {
MinMax(l + 1, r - 1, &mn, &mx);
ans = max(ans, max(r - mx - (lnl)(mx == -1)*inf, mn - l));
l = mn, r = mx;
}
return max(ans, r - l);
}
lnl a = (r - l - 3 + N) / (N - 1);
k = l;
while (l < r) {
MinMax(l, min(l + a, r), &mn, &mx);
if (~mn) {
ans = max(ans, mn - k);
k = mx;
}
l += a + 1;
}
return max(ans, r - k);
}
