#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
void MinMax(long long, long long, long long*, long long*);
*/
long long findGap(int T, int N) {
if (T == 1) {
ll ans = 0;
vector<ll> ini, end;
ll l=0, r=1e18;
while (true) {
MinMax(l, r, &l, &r);
if (l == -1) break;
ini.push_back(l); end.push_back(r);
l++; r--;
}
reverse(end.begin(), end.end());
ll last = ini[0];
for (ll p : ini) {
ans = max(ans, p-last);
last = p;
}
for (ll p : end) {
ans = max(ans, p-last);
last = p;
}
return ans;
}
ll L=0, R=0;
MinMax(0LL, (ll)1e18, &L, &R);
ll sz = (R-L+N-2) / (N - 1);
ll l = L, r = L + sz;
ll ans = sz;
ll last = L;
for (int i=0; i<N-1; i++, l = l+sz+1, r = min(R, r + sz+1)) {
// cout << l << ' ' << r << '\n';
ll a=0, b=0;
MinMax(l, r, &a, &b);
if (a == -1) continue;
ans = max(ans, a - last);
last = b;
if (r == R) break;
}
return ans;
}
