#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p<<' ';cerr<<endl;
#define pb push_back
set<int> s;
int ans=0;
void sol(int l,int r){
if(r-l+2<ans)return;
if(l>r)return;
int mn,mx;
MinMax(l,r,&mn,&mx);
if(mn==-1){
ans=max(ans,r-l+2);
return;
}if(mn==mx){
s.insert(mn);
ans=max({ans,mn-l,r-mn});
return;
}
s.insert(mn);
s.insert(mx);
int x=(mx-mn-1)/3;
sol(mn+1,mn+x);
sol(mn+x+1,mn+x+x);
sol(mn+x+x+1,mx-1);
}
long long findGap(signed T, signed N) {
sol(0,(int)(1e18));
vi v;
for(auto i:s)v.pb(i);
//int ans=0;
for(int i=0;i<sz(v)-1;i++){
ans=max(ans,v[i+1]-v[i]);
}
return ans;
}
