#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#include "gap.h"
const ll MAXN = 100005;
ll findGap(int T, int N) {
if (T == 2) {
ll mn, mx;
MinMax(0, 1e18, &mn, &mx);
ll x = ceil(double ((mx - 1) - (mn + 1)) / double(N - 1)); // can't do N-2 because 2-2 = 0 -> RTE
ll maxr = mx - 1;
ll l = mn + 1;
vector<ll> simga = {mn};
while(l <= maxr) {
MinMax(l, min(maxr, l + x), &mn, &mx);
if (mn != -1) {
simga.push_back(mn);
simga.push_back(mx);
}
l = min(maxr, l + x) + 1;
}
simga.push_back(maxr + 1);
ll res = 0;
FOR(i, (ll)simga.size() - 1) {
res = max(res, simga[i+1] - simga[i]);
}
return res;
} else {
ll mn, mx;
ll l = 0, r = 1e18;
ll il = 0, ir = N-1;
vector<ll> simga(N);
while(il <= ir) {
MinMax(l, r, &mn, &mx);
simga[il] = mn;
simga[ir] = mx;
l = mn + 1;
r = mx - 1;
il++; ir--;
}
ll res = 0;
FOR(i, (ll)simga.size() - 1) {
res = max(res, simga[i+1] - simga[i]);
}
return res;
}
}
