#include "gap.h" // oopsie
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
ll findGap(int T, ll N) {
if (T == 1) {
ll v[N];
int a = 0, b = N - 1;
ll s = 0, t = 1e18, mn, mx;
while (a <= b) {
MinMax(s, t, &mn, &mx);
v[a] = mn;
v[b] = mx;
// a . . . . b N = 6
// ) a . . b ( N = 6
// ) ) a b ( ( N = 6
s = mn + 1; // s > mn
t = mx - 1; // t < mx
a++;
b--;
}
ll res = 0;
FOR(i,0,N-1) res = max(res, v[i+1] - v[i]);
return res;
} else {
ll s = 0, t = 1e18;
ll mn, mx;
MinMax(s, t, &mn, &mx);
if (N == 2) return mx - mn;
ll len = mx - mn + 1;
s = mn + 1;
ll pr = mn, res = 0;
// iterate over the array in (i+1, i) pairs
FOR(i,0,N-1) {
// s
// (X X) jump
// t
t = s + len / (N - 1);
MinMax(s, t, &mn, &mx);
if (mn != -1) {
res = max(res, mn - pr);
pr = mx;
}
// jump after prev group
// (X X) jump
// t
s = t + 1;
}
return res;
}
}