#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long findGap(int T, int N)
{
if (T == 2) {
// Step 1, find A1 and An
ll l, r;
MinMax(0, 1e18, &l, &r);
ll sz = (r-l+N-2)/(N-1);
vector<ll> relevant = {l, r};
for (ll i = l+1; i < r; i += sz) {
// l = i, r = i+sz-1;
ll l1, r1;
MinMax(i, i+sz-1, &l1, &r1);
if (l1 != -1) relevant.push_back(l1), relevant.push_back(r1);
}
sort(relevant.begin(), relevant.end());
ll ans = 0;
for (int i = 0; i+1 < relevant.size(); i ++) ans = max(ans, relevant[i+1] - relevant[i]);
return ans;
}
ll l, r;
MinMax(0, 1e18, &l, &r);
vector<ll> has;
// cout << l << " " << r << "\n";
int know = 2;
while (l+1 <= r-1 and know < N) {
has.push_back(l);
has.push_back(r);
ll a, b;
MinMax(l+1, r-1, &a, &b);
l = a, r = b;
know += 2;
// cout << l << " " << r << "\n";
}
if (l != -1) has.push_back(l);
if (l != r) has.push_back(r);
sort(has.begin(), has.end());
ll ans = 0;
for (int i = 0; i+1 < has.size(); i ++) ans = max(ans, has[i+1] - has[i]);
return ans;
}
