#include<bits/stdc++.h>
using namespace std;
#include "gap.h"
long long mas[100011];
long long findGap(int T,int N){
if(T==1){
long long maxa=1e18+1;
long long ans=0;
long long l=0,r=1e18;
long long L=0,R=N-1;
while(L<=R){
//long long k1,k2;
MinMax(l,r,&mas[L],&mas[R]);
L++;
R--;
l=mas[L-1]+1;
r=mas[R+1]-1;
}
for(int i=0;i<N-1;i++){
if(mas[i+1]-mas[i]>ans){
ans=mas[i+1]-mas[i];
}
}
return ans;
}
long long k1,k2;
long long l=0,r=1e18;
MinMax(l,r,&k1,&k2);
if(N==2){
return k2-k1;
}
l=k1+1;
r=k2-1;
long long dul=(r-l+1)/(N-1);
long long L=l,R=min(L+dul-1,r-1);
long long pre=l-1;
long long otg=0;
for(int i=0;R<r && L<r;i++){
MinMax(L,R,&k1,&k2);
if(k1!=-1){
otg=max(otg,(k1-pre));
otg=max(otg,(k2-k1));
pre=k2;
}
L+=dul;
R=min(L+dul-1,r-1);
}
return max(otg,(r+1)-pre);
}
