#include "gap.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)
using namespace std;
ll findGap(int t, int n) {
if(t == 1) {
vector <ll> v;
ll L = 0;
ll R = 1e18;
while(L <= R) {
ll LL, RR;
MinMax(L, R, &LL, &RR);
if(LL == -1) break;
v.pb(LL);
if(LL != RR)
v.pb(RR);
if(ss(v) == n)
break;
L = LL + 1;
R = RR - 1;
}
sort(v.begin(), v.end());
ll ans = 0;
for(int i = 0; i + 1 < ss(v); ++i)
ans = max(ans, v[i + 1] - v[i]);
return ans;
}
// t = 2
ll L = 0;
ll R = 1e18;
ll LL, RR;
MinMax(L, R, &LL, &RR);
ll ans = (RR - LL + n - 2) / (n - 1);
ll Last = -1;
L = LL;
R = RR;
ll P = ans;
while(L <= R) {
MinMax(L, L + P, &LL, &RR);
if(LL == -1) {
L += P + 1;
continue;
}
if(Last != -1) {
ans = max(ans, LL - Last);
}
Last = RR;
L += P + 1;
}
return ans;
}
