#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
long long findGap(int T,int N){
if(T==1){
long long arr[N];
int a=0,b=N-1;
long long s=0,t=1000000000000000000;
long long mn,mx;
while(a<=b){
MinMax(s,t,&mn,&mx);
arr[a]=mn;
arr[b]=mx;
s=mn+1;
t=mx-1;
a++; b--;
}
long long ans=0;
for(int i=1;i<N;i++){
ans=max(ans,arr[i]-arr[i-1]);
}
return ans;
}else{
long long s=0,t=1000000000000000000;
long long mn,mx;
MinMax(s,t,&mn,&mx);
if(N==2)return mx-mn;
long long k=mx-mn+1;
s=mn+1;
long long prev=mn,ans=0;
for(int i=0;i<N-1;i++){
t=s+(k/(N-1));
MinMax(s,t,&mn,&mx);
if(mn!=-1){
ans=max(ans,mn-prev);
prev=mx;
}
s=t+1;
}
return ans;
}
}
