#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
set<long long> x;
int N, sz;
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)
{
long long l, r, x, y, mn, mx;
MinMax(1, (long long)1e18, &mx, &mx);
long long st = (mx - mn + n - 2) / (n - 1), ls = l;
long long ans = st, i;
for(i = mn; i + st < mx; i += st + 1){
MinMax(i, i + st, &x, &y);
if(x != -1){
ans = max(ans, x - ls);
ls = y;
}
}
MinMax(i, mx, &x, &y);
if(x != -1) ans = max(ans, x - ls);
return ans;
}
