#include "gap.h"
#include <bits/stdc++.h>
#define ff(i,a,b) for(int i = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int i = (a); (i) >= (b); --(i))
#define pb push_back
#define ll long long
using namespace std;
ll findGap(int t, int n){
if(t == 1){
vector<ll> niz;
ll l,r;
MinMax(0, 1e18, &l, &r);
niz.pb(l);
niz.pb(r);
ff(i,1,(n-1)/2){
MinMax(l + 1, r - 1, &l, &r);
if(l != -1)niz.pb(l);
if(r != -1 && l != r)niz.pb(r);
}
sort(niz.begin(), niz.end());
ll ans = 0;
ff(i,0,n-1)ans = max(ans, niz[i + 1] - niz[i]);
return ans;
}
else{
vector<ll> niz;
ll l,r;
MinMax(0, 1e18, &l, &r);
if(n == 2)return r - l;
niz.pb(l);
niz.pb(r);
ll d = (r - l + n - 3) / (n - 2);
for(ll i = l + 1; i < r; i += d){
ll x,y;
MinMax(i, i + d - 1, &x, &y);
if(x != -1)niz.pb(x);
if(y != -1 && x != y)niz.pb(y);
}
sort(niz.begin(), niz.end());
niz.erase(unique(niz.begin(), niz.end()), niz.end());
ll ans = 0;
ff(i,0,niz.size()-1)ans = max(ans, niz[i + 1] - niz[i]);
return ans;
}
}
