#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
vector<ll> qs;
pair<ll, ll> query(ll lo, ll hi) {
pair<ll, ll> res;
MinMax(lo, hi, &res.first, &res.second);
/// cerr << "q " << lo << " " << hi << endl;
if (res.first != -1) {
qs.push_back(res.first);
if (res.first != res.second) qs.push_back(res.second);
}
return res;
}
long long findGap(int T, int N) {
if (T == 1) {
ll lo = 0;
ll hi = 1'000'000'000'000'000'000;
for (int i = 0; i < (N + 1) / 2 && lo <= hi; ++i) {
tie(lo, hi) = query(lo, hi);
++lo; --hi;
}
}
if (T == 2) {
ll lo = 0;
ll hi = 1'000'000'000'000'000'000;
tie(lo, hi) = query(lo, hi);
++lo;
--hi;
for (int k = N - 1; k >= 1; --k) {
ll nask = lo + (hi - lo) / k;
query(lo, nask);
lo = nask + 1;
}
}
sort(all(qs));
ll res = 0;
rep(i,0,sz(qs) - 1) res = max(res, qs[i + 1] - qs[i]);
return res;
}
