#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
long long findGap(int T, int N)
{
if(T==1||N<=8){
vector<long long>all(N);
long long mn=-1,mx=((long long)1e18+5),fmn=0,fmx=0;
//cout<<mx<<"\n";
int last=N-1,first=0;
while(last>=first){
MinMax(mn+1,mx-1,&fmn,&fmx);
//cout<<first<<" "<<last<<" "<<mn+1<<" "<<mx-1<<" "<<fmn<<" "<<fmx<<'\n';
mn=fmn;
mx=fmx;
all[last]=mx;
all[first]=mn;
last--;
first++;
}
long long res=0;
for(int i=1;i<N;i++){
// cout<<all[i]<<" "<<all[i-1]<<'\n';
res=max(res,all[i]-all[i-1]);
}
return res;
}
else{
long long res=1;
long long mn=-1,mx=((long long)1e18+5),fmn=0,fmx=0;
MinMax(mn+1,mx-1,&fmn,&fmx);
mn=fmn;
mx=fmx;
res=(mx-mn)/N;
while(mn+res-1<mx){
//cout<<mn<<" asda "<<res<<endl;
MinMax(mn+1,mn+res,&fmn,&fmx);
//cout<<fmn<<" edasdb "<<fmx<<endl;
if(fmn==-1){
break;
}
mn=fmx;
}
//cout<<mn<<" "<<mx<<endl;
while(mn+res-1<mx){
//cout<<mn<<" asd "<<res<<endl;
MinMax(mn+res,mn+res+res,&fmn,&fmx);
if(fmn==-1){
res*=2;
res++;
continue;
}
res=max(res,fmn-mn);
mn=fmx;
while(mn+res-1<mx){
//cout<<mn<<" asda "<<res<<endl;
MinMax(mn+1,mn+res,&fmn,&fmx);
//cout<<fmn<<" edasdb "<<fmx<<endl;
if(fmn==-1){
break;
}
mn=fmx;
}
//cout<<mn<<" asdb "<<res<<endl;
}
//cout<<res<<endl;
return res;
}
}
