#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
long long findGap(int T, int N) {
int n = N;
if (T == 1) {
vector<ll> a;
ll mn = -1, mx = 1e18; mx += 5;
for (int i = 0; ; i++) {
MinMax(mn + 1, mx - 1, &mn, &mx);
if (mn == mx) a.emplace_back(mn);
else {
a.emplace_back(mn);
a.emplace_back(mx);
}
if (a.size() == n) break;
}
sort(a.begin(), a.end());
ll ans = 0;
for (int i = 0; i < a.size() - 1; i++) ans = max(ans, a[i + 1] - a[i]);
return ans;
} else {
vector<ll> a;
ll mn = -1, mx = 1e18; mx += 5;
MinMax(0, 1e18, &mn, &mx);
if (n == 2) return mx - mn;
ll z = (mx - mn - 1) / (n - 1);
vector<pii> p, r;
ll s = mn + 1;
while (s + z - 1 < mx) {
p.emplace_back(s, s + z - 1); s += z;
}
if (s != mx) p.emplace_back(s, mx - 1);
for (auto &[x, y]: p) {
ll mno, mxo;
MinMax(x, y, &mno, &mxo);
r.emplace_back(mno, mxo);
}
int csz = p.size();
ll ans = 0;
vector<pii> np, nr;
ll st = 1e18, ed = -1; st += 5;
for (int i = 0; i < csz; i++) {
if (r[i] == pii(-1, -1)) {
st = min(st, p[i].first);
ed = max(ed, p[i].second);
} else {
if (ed != -1) {
np.emplace_back(st, ed);
nr.emplace_back(-1, -1);
}
np.emplace_back(p[i]);
nr.emplace_back(r[i]);
st = ed = -1;
}
}
csz = np.size();
for (int i = 0; i < csz; i++) {
if (nr[i] == pii(-1, -1)) {
auto [cmn, cmx] = np[i];
if (i - 1 >= 0) cmn = np[i - 1].second;
else cmn = mn;
if (i + 1 < csz) cmx = np[i + 1].first;
else cmx = mx;
ans = max(ans, cmx - cmn);
}
}
return ans;
}
return 0;
}
