#include "gap.h"
#include <vector>
#include <algorithm>
using ll = long long;
using namespace std;
const ll INF = 1.77013e18;
void find_recur(ll mn, ll mx, ll& maxdif) {
if (mx - mn <= maxdif)
return;
if (mx - mn == 2) {
ll nmn, nmx;
MinMax(mn + 1, mx - 1, &nmn, &nmx);
if (nmn == -1)
maxdif = max(maxdif, 2ll);
return;
}
ll md = (mn + mx) / 2;
ll lmn, lmx;
MinMax(mn + 1, md, &lmn, &lmx);
ll rmn, rmx;
MinMax(md + 1, mx - 1, &rmn, &rmx);
if (lmn == -1 && rmn == -1) {
maxdif = max(maxdif, mx - mn);
return;
}
if (lmn == -1) {
maxdif = max(maxdif, rmn - mn);
return;
}
if (rmn == -1) {
maxdif = max(maxdif, mx - lmx);
return;
}
maxdif = max({maxdif, lmn - mn, rmn - lmx, mx - rmx});
if (lmx - lmn < rmx - rmn) {
find_recur(rmn, rmx, maxdif);
find_recur(lmn, lmx, maxdif);
} else {
find_recur(lmn, lmx, maxdif);
find_recur(rmn, rmx, maxdif);
}
}
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 if (N <= 10) {
ll mn, mx;
MinMax(1ll, INF, &mn, &mx);
ll ans = (mx - mn - 1) / (N - 1) + 1;
find_recur(mn, mx, ans);
return ans;
} else {
ll sgcnt = N * 7 / 5;
ll sglen = (INF - 2) / N + 1;
vector<ll> mn(sgcnt);
vector<ll> mx(sgcnt);
for (ll i = 0; i < sgcnt; ++i) {
MinMax(1 + i * sglen, (i + 1) * sglen, &mn[i], &mx[i]);
}
ll ans = 0;
for (int i = 0; i + 1 < sgcnt; ++i) {
if (mn[i] == -1)
continue;
int j = i + 1;
while (mn[j] == -1 && j < sgcnt)
++j;
if (j != sgcnt) {
ans = max(ans, mn[j] - mx[i]);
}
}
for (int i = 0; i < sgcnt; ++i) {
if (mn[i] != -1)
find_recur(mn[i], mx[i], ans);
}
return ans;
}
return 0;
}
