#include "gap.h"
#include <bits/stdc++.h>
typedef long long ll;
ll Min, Max, s, t;
ll findGap(int T, int N) {
if (T == 1) {
s = 0, t = 1e18;
ll arr[N];
int l = 0, r = N - 1;
while (l <= r) {
MinMax(s, t, &Min, &Max);
arr[l] = Min, arr[r] = Max;
s = Min + 1, t = Max - 1;
l++, --r;
}
ll ans = 0;
for (int i = 1; i < N; ++i) {
ans = std::max(ans, arr[i] - arr[i - 1]);
}
return ans;
} else {
s = 0, t = 1e18;
MinMax(s, t, &Min, &Max);
ll step = ((Max - Min + 1) + (N - 1)) / (N - 1) - 1;
ll l = Min, i, x, y, ans = step;
for (i = Min; i + step < Max; i += step + 1) {
MinMax(i, i + step, &x, &y);
if (x != -1) {
ans = std::max(ans, x - l);
l = y;
}
}
MinMax(i, Max, &x, &y);
if (x != -1) {
ans = std::max(ans, x - l);
}
return ans;
}
}
