#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<vector>
#include<assert.h>
#include<algorithm>
#include "gap.h"
using namespace std;
vector<long long> num;
long long findGap(int T,int N){
long long i;
if(T==1){
long long i,maxv=1000000000000000000,minv=0,ans,ans2;
while(maxv>=minv&&num.size()<N){
MinMax(minv,maxv,&ans,&ans2);
if(ans==-1||ans2==-1)
break;
if(ans==ans2){
num.emplace_back(ans);
break;
}
num.emplace_back(ans);
num.emplace_back(ans2);
maxv=ans2-1;
minv=ans+1;
}
sort(num.begin(),num.end());
ans=0;
for(i=1;i<num.size();i++)
ans=max(ans,num[i]-num[i-1]);
return ans;
}
else{
long long minv,maxv;
MinMax(0,1000000000000000000,&minv,&maxv);
long long block=(maxv-minv)/(N-1);
long long ans=block,pre=minv,l,r;
for(i=minv+1;i+block-1<maxv;i+=block){
MinMax(i,i+block-1,&l,&r);
if(pre!=-1&&l!=-1)
ans=max(ans,l-pre);
if(r!=-1)
pre=r;
}
if(i<maxv&&pre!=-1){
MinMax(i,maxv-1,&l,&r);
if(l==-1)
l=maxv;
ans=max(ans,l-pre);
}
else if(i==maxv&&pre!=-1)
ans=max(ans,maxv-pre);
return ans;
}
}
