#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long findGap(int T, int N) {
if (T == 1) {
long long lx = 0;
long long rx = (long long)1e18;
long long a[N] = {};
int lt = 0;
int rt = N - 1;
while (lt <= rt) {
long long tl = lx;
long long tr = rx;
MinMax(tl, tr, &lx, &rx);
a[lt] = lx;
a[rt] = rx;
lx++;
rx--;
lt++;
rt--;
}
long long d = 0;
for (int i = 1; i < N; i++) {
d = max(d, a[i] - a[i - 1]);
}
return d;
}
else {
long long lx, rx;
long long tl = 0;
long long tr = (long long)1e18;
MinMax(tl, tr, &lx, &rx);
long long d = 0;
long long cc = lx;
long long h = (rx - lx - 1) / (N - 1) + 1;
for (int i = 0; i < N - 1; i++) {
long long xa = h * i + lx;
long long xb = h * (i + 1) + lx;
if (xa > xb) {
continue;
}
MinMax(xa, xb, &tl, &tr);
if (tl == -1) {
continue;
}
d = max(d, tl - cc);
cc = tr;
}
return d;
}
}
