#include "gap.h"
#include <vector>
#include <cstdio>
#include <climits>
using namespace std;
typedef long long ll;
long long findGap(int T, int N)
{
if (T == 1) {
ll mn = 0, mx = LLONG_MAX;
vector<ll> lf, rg;
for (int i = 0; i < N / 2; i++) {
MinMax(mn, mx, &mn, &mx);
lf.push_back(mn++);
rg.push_back(mx--);
}
if (N % 2) {
MinMax(mn, mx, &mn, &mx);
lf.push_back(mn);
}
auto it = rg.rbegin();
for (; it != rg.rend(); it++)
lf.push_back(*it);
ll ans = 1;
for (int x = 0; x < N - 1; x++)
ans = max(ans, lf[x + 1] - lf[x]);
return ans;
}
ll mn = 0, mx = LLONG_MAX;
MinMax(mn, mx, &mn, &mx);
ll mx2 = mx;
ll i = mn, step = (mx - mn + N - 2) / (N - 1),
ans = step, l = mn;
for (; i + step < mx; i += step + 1) {
MinMax(i, i + step, &mn, &mx);
if (mn != -1) {
ans = max(ans, mn - l);
l = mx;
}
}
MinMax(i, mx2, &mn, &mx);
if (mn != -1)
ans = max(ans, mn - l);
return ans;
}
