#include "gap.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
long long findGap(int T, int N) {
if(T == 1) {
long long mn, mx;
MinMax(1, 1e18, &mn, &mx);
vector<long long> a(N + 1);
a[1] = mn, a[N] = mx;
for(int l = 2, r = N - 1; l <= r; ++l, --r) {
MinMax(mn + 1, mx - 1, &a[l], &a[r]);
mn = a[l], mx = a[r];
}
long long res = 0;
for(int i = 2; i <= N; ++i) {
res = max(res, a[i] - a[i - 1]);
}
return res;
} else {
long long mn, mx;
MinMax(1, 1e18, &mn, &mx);
long long b = (mx - mn + N - 2) / (N - 1) + 1;
long long prv = mn, res = -1;
long long l, r;
for(long long i = mn; i <= mx; i += b) {
if(i + b > mx) {
MinMax(i, mx, &l, &r);
if(l != -1) {
res = max(res, l - prv);
}
} else {
MinMax(i, i + b - 1, &l, &r);
if(l != -1 and r != -1) {
res = max(res, l - prv);
prv = r;
}
}
}
return res;
}
}
