#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
//void MinMax(s,t,&mn,&mx)
long long findGap(int TT, int n){
if(TT==1){
//long long s,t,&mn,&mx;
vector<long long>dn(n);
MinMax(0,1000000000000000000LL,&dn[0],&dn[n-1]);
for(int i=1;i<n/2;i++){
MinMax(dn[i-1]+1,dn[n-i]-1,&dn[i],&dn[n-i-1]);
}
if(n%2==1){
MinMax(dn[n/2-1]+1,dn[n/2+1]-1,&dn[n/2],&dn[n/2]);
}
long long mn=0LL;
for(int i=0;i<n-1;i++){
mn=max(mn,dn[i+1]-dn[i]);
}
return mn;
}else{
long long a,b;
MinMax(0,1000000000000000000LL,&a,&b);
long long d=(b-a-1)/(n-1);
long long x=(b-a-1)-d*(n-1);
long long y=n-1-x;
long long ma=0,xx=a,p=a+1;//pointer
for(int i=0;i<n-1;i++){
long long mn,mx;
if(i<y){
MinMax(p,p+d,&mn,&mx);
p+=d;
}else{
MinMax(p,p+d+1,&mn,&mx);
p+=d+1;
}
if(mn!=-1){
ma=max(ma,mn-xx);
xx=mx;
}
}
ma=max(ma,b-xx);
return ma;
}
}
