#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 xa = 1;
long long xb = rx - lx;
if (xa % (N - 1) != 0) {
xa = (xa / (N - 1) + 1) * (N - 1);
}
if (xb % (N - 1) == 0) {
xb = xb - 1;
}
else {
xb = xb / (N - 1) * (N - 1);
}
xa += lx;
xb += lx;
if (xa <= xb) {
MinMax(xa, xb, &tl, &tr);
}
cc = tr;
for (int i = 1; i < N; i++) {
xa = (rx - lx) * i;
xb = (rx - lx) * (i + 1);
if (xa % (N - 1) != 0) {
xa = (xa / (N - 1) + 1) * (N - 1);
}
if (xb % (N - 1) == 0) {
xb = xb - 1;
}
else {
xb = xb / (N - 1) * (N - 1);
}
xa += lx;
xb += lx;
if (xa > xb) {
continue;
}
MinMax(xa, xb, &tl, &tr);
if (tl == -1) {
continue;
}
d = max(d, tl - cc);
cc = tr;
}
return d;
}
}
