#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll findGap(int T, int N) {
const ll inf = 1'000'000'000'000'000'000LL;
ll mn = -1, mx = inf + 1;
if (T == 1) {
vector<ll> a(N);
ll ans = -inf;
for (int l = 0, r = N - 1; l <= r; ++l, --r) {
MinMax(mn + 1, mx - 1, &mn, &mx);
assert(mn != -1);
a[l] = mn, a[r] = mx;
}
for (int i = 0; i < N - 1; ++i) {
ans = max(ans, a[i + 1] - a[i]);
}
return ans;
} else {
MinMax(0, inf, &mn, &mx);
ll sum = mx - mn;
ll ans = -inf;
ll len = (sum + (N - 1) - 1) / (N - 1);
ll R = mx;
for (int i = N - 1; i > 0; --i) {
ll nw = mx;
MinMax(mx - len, mx - 1, &mn, &mx);
if (mx != -1) {
ans = max(ans, R - mx);
R = mn;
}
mx = nw - len;
}
return ans;
}
}
