#include "gap.h"
#include <vector>
#include <algorithm>
#include <random>
using ll = long long;
using namespace std;
mt19937 rng(time(0));
const ll INF = 1.77013e18;
ll findGap(int T, int N) {
if (T == 1) {
vector<ll> mn;
vector<ll> mx;
while (mn.size() + mx.size() < N) {
ll nmn, nmx;
if (mn.empty()) {
MinMax(1ll, INF, &nmn, &nmx);
} else {
MinMax(mn.back() + 1, mx.back() - 1, &nmn, &nmx);
}
mn.push_back(nmn);
if (nmn != nmx)
mx.push_back(nmx);
}
reverse(mx.begin(), mx.end());
for (auto x : mx) {
mn.push_back(x);
}
ll ans = 0;
for (int i = 0; i + 1 < N; ++i) {
ans = max(ans, mn[i + 1] - mn[i]);
}
return ans;
} else {
ll mn, mx;
MinMax(1, INF, &mn, &mx);
ll ans = (mx - mn - 1) / (N - 1) + 1;
ll mxans = mx - mn;
ll curvl = mn;
vector<pair<ll, ll>> gaps;
while (ans < mxans && curvl < mx) {
ll nmn, nmx;
MinMax(curvl + 1, curvl + ans * 2 - 1, &nmn, &nmx);
if (nmn != -1) {
ans = max(ans, nmn - curvl);
gaps.push_back({nmn, nmx});
curvl = nmx;
} else {
ans *= 2;
}
}
shuffle(gaps.begin(), gaps.end(), rng);
for (auto [l, r] : gaps) {
if (r - l > ans) {
ll md = (l + r) / 2;
ll lmn, lmx;
MinMax(l + 1, md, &lmn, &lmx);
if (lmx != -1 && r - lmx <= ans)
continue;
ll rmn, rmx;
MinMax(md + 1, r - 1, &rmn, &rmx);
if (lmn == -1 && rmn == -1) {
ans = r - l;
} else if (lmn == -1) {
ans = max(ans, rmn - l);
} else if (rmn == -1) {
ans = max(ans, r - lmx);
} else {
ans = max(ans, rmn - lmx);
}
}
}
return ans;
}
return 0;
}
