#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int findGap(int32_t tc, int32_t n) {
if (tc == 1) {
int s = 0, t = 1e18;
int l = 1, r = n;
int a[n];
while (l <= r) {
int mn, mx;
MinMax(s, t, &mn, &mx);
a[l++] = mn;
a[r--] = mx;
s = mn + 1;
t = mx - 1;
}
int ans = 0;
for (int i = 2; i <= n; i++) {
ans = max(ans, a[i] - a[i - 1]);
}
return ans;
}
int s = 0, t = 1e18;
int mn, mx;
MinMax(s, t, &mn, &mx);
vector<int> v;
int part = (mx - mn + n - 2) / (n - 1);
for (int i = mn; i <= mx; i += part + 1) {
int a, b;
MinMax(i, i + part, &a, &b);
if (a != -1) {
v.push_back(a);
v.push_back(b);
}
}
int ans = part;
for (int i = 1; i < v.size(); i++) {
ans = max(ans, v[i] - v[i - 1]);
}
return ans;
}
