#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long solve(int n)
{
long long f,l,ans=0;
MinMax(0,1e18,&f,&l);
deque<long long> d1({f}),d2({l});
while (d1.size()+d2.size()<n)
{
MinMax(f+1,l-1,&f,&l);
d1.push_back(f);
d2.push_front(l);
}
for (int i=1;i<d1.size();i++)
ans=max(ans,d1[i]-d1[i-1]);
for (int i=1;i<d2.size();i++)
ans=max(ans,d2[i]-d2[i-1]);
return max(ans,d2.front()-d1.back());
}
long long findGap(int t,int n)
{
if (t==1 || n<=10)
return solve(n);
long long f,l;
MinMax(0,1e18,&f,&l);
long long p=f+1,g=1;
while (p<=l)
{
long long mn,mx;
MinMax(p,p+g-1,&mn,&mx);
if (mn==-1)
{
while (mn==-1)
{
g*=2;
MinMax(p,p+g,&mn,&mx);
}
g=mn-p+1;
}
p=mx+1;
}
return g;
}
