#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,ans;
ll solve(){
ll apa[n+1];
ll mn,mx;
MinMax(0,1e18,&mn,&mx);
apa[1]=mn,apa[n]=mx;
for(int l=2,r=n-1;l<=r;l++,r--){
mn++,mx--;
MinMax(mn,mx,&mn,&mx);
apa[l]=mn,apa[r]=mx;
}
ll ans=0;
for(int q=1;q<n;q++){
ans=max(ans,apa[q+1]-apa[q]);
}
return ans;
}
ll findGap(int T, int N){
n=N;
if(T==1){
return solve();
}
ll mn,mx;
MinMax(0,1e18,&mn,&mx);
ll grup=(mx-mn)/(n-1);
ans=grup;
ll satu,dua,lst;
lst=mn;
for(satu=mn+1,dua=mn+grup;satu<=mx;satu+=grup,dua+=grup){
dua=min(dua,mx);
ll apa1,apa2;
MinMax(satu,dua,&apa1,&apa2);
if(apa1==-1)continue;
ans=max(ans,apa1-lst);
lst=apa2;
}
return ans;
}
