#include "gap.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define ll long long
ll a[200005],inf=1e18;
ll mx,mn;
long long findGap(int T, int N){
if(T==1){
ll l=0,r=N,x=0,y=inf;
while(l<r){
MinMax(x,y,&mn,&mx);
a[l++]=mn,a[--r]=mx;
x=mn+1;
y=mx-1;
}
ll ans=0;
for(int i=0;i<N-1;i++)
ans=max(ans,a[i+1]-a[i]);
return ans;
}
else{
MinMax(1,1e18,&mn,&mx);
if(N==2)
return mx-mn;
ll sz=(mx-mn-1);
ll s=mn+1,last=mn,ans=0;
for(int i=0;i<N-1;i++){
ll tmp=s+sz/(N-1)-1;
if(i<sz%(N-1)) tmp++;
MinMax(s,tmp,&mn,&mx);
if(mn!=-1){
ans=max(ans,mn-last);
last=mx;
}
s=tmp+1;
}
return max(ans,s-last);
}
//return 0;
}
