#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
long long solve(int N) {
long long l, r, res = 0;
MinMax(0, 1e18, &l, &r);
for (int i = 1; i <= (N - 1) / 2; i++) {
long long nl, nr;
MinMax(l + 1, r - 1, &nl, &nr);
res = max(res, nl - l), l = nl;
res = max(res, r - nr), r = nr;
}
return max(res, r - l);
}
long long findGap(int T, int N) {
if (T == 1)
return solve(N);
long long l, r;
MinMax(0, 1e18, &l, &r);
long long res = (r - l - 1) / (N - 1) + 1;
for (long long nl, nr; l < r; l = nr) {
MinMax(l + 1, l + res, &nl, &nr);
if (nr != -1) continue ;
MinMax(l + 1, l + (res + 1) * 2, &nl, &nr);
while (nl == -1) {
res = (res + 1) * 2 + 1;
MinMax(l + 1, l + (res + 1) * 2, &nl, &nr);
}
res = nl - l;
}
return res;
}
