#include "gap.h"
#define ll long long
#include<iostream>
using namespace std;
template<class T>
inline bool chmax(T &a,T b){
if(a<b){a=b;return true;}
return false;
}
ll solve1(int N){
ll ans=0;
ll l=-1,r=1e18;r+=1;
for(int i=0;i<(N+1)/2;i++){
ll mn,mx;
MinMax(l+1,r-1,&mn,&mx);
if(i){
chmax(ans,mn-l);
chmax(ans,r-mx);
}
l=mn;
r=mx;
}
if(N%2==0)chmax(ans,r-l);
return ans;
}
ll solve2(int N){
ll mn,mx;
MinMax(0,1e18,&mn,&mx);
ll ans=0,now=mn,mxx=mx;
for(int i=0;i<N-1;i++){
int ok=0,ng=-1;
while(now+(1ll<<ok)<=1e18)ok++;
while(ok-ng>1){
int mid=(ok+ng)/2;
MinMax(now+1,now+(1ll<<mid),&mn,&mx);
if(mn!=-1){
chmax(ans,mn-now);
now=mn;
goto ok;
}
ng=mid;
}
MinMax(now+1,now+(1ll<<ok),&mn,&mx);
chmax(ans,mn-now);
now=mn;
ok:;
}
chmax(ans,mxx-mn);
return ans;
}
ll findGap(int T, int N){
if(T==1)return solve1(N);
return solve2(N);
}
