#include "gap.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
long long findGap(int T, int n)
{
ll L,R;
MinMax(1ll,(ll)1e18,&L,&R);
if(T==1){
ll ans=0;
if(n==2){
ans=R-L;
return ans;
}
for(int i=0;i<(n+1)/2-1;i++){
ll L1,R1;
MinMax(L+1,R-1,&L1,&R1);
ans=max({ans,L1-L,R-R1});
L=L1;
R=R1;
}
if(n%2==0){
ans=max(ans,R-L);
}
return ans;
}
ll gap=(R-L-1+(n-1)-1)/(n-1);
vector<pair<ll,ll>> vec;
vec.push_back({L,L});
for(ll l=L+1;l<R;l+=gap){
ll r=min(R-1,l+gap-1);
ll mn,mx;
MinMax(l,r,&mn,&mx);
if(mn!=-1)vec.push_back({mn,mx});
}
vec.push_back({R,R});
ll ans=0;
int sz=(int)vec.size();
for(int i=0;i<sz-1;i++){
ans=max(ans,vec[i+1].f-vec[i].s);
}
return ans;
}
