#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
map<long long,bool> vis;
vector<long long> v;
long long findGap(int T, int N)
{ long long ans = 0;
if(T == 1){
long long mn=0,mx=0;
long long s = 0 , e = 1e18;
for(int i=0;i<(N+1)/2;i++){
MinMax(s,e,&mn,&mx);
if(!vis[mn])
v.push_back(mn);
vis[mn] = true;
if(!vis[mx])
v.push_back(mx);
vis[mx] = 1;
s = mn+1;
e = mx-1;
}
sort(v.begin(),v.end());
int si = v.size();
for(int i=0;i<si-1;i++){
ans = max(ans,v[i+1]-v[i]);
}
}
else{
long long s,e;
MinMax(0,1e18,&s,&e);
long long step = (e-s)/(N-1);
ans = step;
long long mn,mx;
for(long long i = s+step+1;i<e;){
for(;i<e;i+=step){
MinMax(s+1,i,&mn,&mx);
if(mx != -1)
break;
}
long long f = mx;
if(i >= e){
f = e;
MinMax(i-step,f,&mn,&mx);
ans = max(ans,mn-s);
step = ans;
}
else{
ans = max(ans,mn-s);
step = ans;
}
s = f;
i = s + step+1;
}
}
return ans;
}
