#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
set<long long> x;
int N;
pair<long long, long long> ask(long long l, long long r){
long long *mn, *mx;
MinMax(l, r, mn, mx);
return {*mn, *mx};
}
void solve(long long l, long long r){
if(l > r || (int) x.size() == N) return;
long long mid1 = l + (r - l) / 3;
long long mid2 = r - (r - l) / 3;
long long mn, mx;
MinMax(l, r, &mn, &mx);
if(mn == -1 || mx == -1) return;
x.insert(mn);
x.insert(mx);
if(l == r) return;
solve(mn + 1, mid1);
solve(mid1 + 1, mid2);
solve(mid2 + 1, mx - 1);
}
long long findGap(int T, int n)
{
N = n;
x.clear();
solve(0ll, (long long) 1e18);
long long ans = 0ll, prev = *x.begin();
for(auto it : x){
ans = max(ans, it - prev);
prev = it;
}
return ans;
}
