#include "bits/stdc++.h"
#include "gap.h"
using namespace std;
const long long maxV = 1e18;
long long findGap(int T, int N)
{
long long mx, mn;
MinMax(0, maxV, &mn, &mx);
long long lower = (mx - mn + N - 2) / (N - 1);
long long cur = mn + 1;
vector <long long> v ({mn});
int cnt = N - 1;
while(cur <= mx) {
long long p, q;
MinMax(cur, min(mx, cur + lower), &p, &q);
cur += lower + 1;
if(p != -1) {
if(!v.empty()) {
lower = max(lower, p - v.back());
}
v.push_back(p);
v.push_back(q);
cnt -= (p == q) ? 1 : 2;
} else {
lower = max(lower, min(mx, cur) - v.back());
}
if(cnt) lower = max(lower, (mx - v.back() + cnt - 1) / cnt);
// cout << cur << " " << min(mx, cur + lower - 1) << " " << p << " " << q << endl;
}
return lower;
}
