#include<bits/stdc++.h>
#include "gap.h"
#define ll long long
using namespace std;
long long findGap(int T,int N){
if(T==1){
ll s=0,t=1e18,mn,mx,ans=0,cnt=2;
MinMax(s,t,&mn,&mx);
s=mn,t=mx;
while(cnt<N){
MinMax(s+1,t-1,&mn,&mx);
cnt+=2;
ans=max(ans,mn-s);
ans=max(ans,t-mx);
s=mn,t=mx;
}
ans=max(ans,t-s);
return ans;
}
ll s=0,t=1e18,mn,mx;
MinMax(s,t,&mn,&mx);
ll L=(mx-mn+N-2)/(N-1);
ll ans=L;
ll lastmax=mn;
for(ll i=mn+1 ; i<mx ; i+=L+1){
ll cmn,cmx;
MinMax(i,min(i+L,mx-1),&cmn,&cmx);
if(cmn!=-1){
ans=max(ans,cmn-lastmax);
lastmax=cmx;
}
}
ans=max(ans,mx-lastmax);
return ans;
}
