#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
typedef pair<int,int> pii;
const int inf = 1e18;
set<int> nums;
void recurse(int s, int e){ //s and e are possible candidates too
int mn, mx;
if(s > e) return;
if(s == e){
MinMax(s,e,&mn,&mx);
if(mn != -1) nums.insert(s);
return;
}
int m = (s+e)/2;
MinMax(s,m,&mn,&mx);
if(mn != -1){
nums.insert(mn);
nums.insert(mx);
recurse(s+1,m-1);
}
MinMax(m+1,e,&mn,&mx);
if(mn != -1){
nums.insert(mn);
nums.insert(mx);
recurse(m+2,e-1);
}
}
long long findGap(signed T, signed N){
recurse(0,inf);
vector<int>v;
for(auto i: nums) v.pb(i);
int ans = 0;
for(int i=0; i<N-1; i++){
ans = max(ans, v[i+1] - v[i]);
}
return ans;
}
