#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll = long long;
long long findGap(int T, int N) {
if(T==1) {
ll l=0, r=1e18;
vector<ll> vec;
for(int i=0; i<(N+1)/2; i++) {
ll mn, mx;
MinMax(l, r, &mn, &mx);
vec.push_back(mn);
vec.push_back(mx);
l=mn+1, r=mx-1;
}
if(vec.size()>N) vec.pop_back();
sort(vec.begin(), vec.end());
ll ans=0;
for(int i=0; i+1<N; i++) ans = max(ans, vec[i+1]-vec[i]);
return ans;
}
else {
ll mn, mx;
MinMax(0, 1e18, &mn, &mx);
ll lb = (mx-mn+N-2)/(N-1);
ll ans = lb, lst=mn;
for(ll i=mn; i<=mx; i += lb+1) {
ll x, y;
MinMax(i, min(i+lb, mx), &x, &y);
if(x!=-1) {
ans = max(ans, x-lst);
lst = y;
}
}
return ans;
}
}
