#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;
ll findGap(int T, int n){
ll l, r;
ll bl = 1, br = inf;
MinMax(0, inf, &l, &r);
set<ll> f;
f.insert(l);
f.insert(r);
auto check = [&](ll m){
if (m == 1) return 1;
ll k = *f.begin();
while (k != *prev(f.end())){
auto it = f.upper_bound(k);
if (it != f.end() && (*it) <= (k + m - 1)) return 0;
MinMax(k + 1, k + m - 1, &l, &r);
if (l == -1) return 1;
f.insert(l);
f.insert(r);
k = r;
}
return 1;
};
while (bl + 1 < br){
ll m = (bl + br) / 2;
if (check(m)){
bl = m;
}
else {
br = m - 1;
}
}
if (check(br)) bl = br;
return bl;
}
