#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll findGap(int T, int N){
if(T == 1){
ll a[N + 1];
for(int i = 0;i<(N + 1) / 2;i++){
ll mn, mx;
if(i == 0){
MinMax(0, (ll)1e18, &mn, &mx);
}else{
MinMax(a[i] + 1, a[N - i + 1] - 1, &mn, &mx);
}
a[i + 1] = mn;
a[N - i] = mx;
}
ll ans = 0;
for(int i = 1;i<N;i++){
ans = max(ans, a[i + 1] - a[i]);
}
return ans;
}else{
vector<ll> a;
ll fi, ls;
MinMax(0, (ll)1e18, &fi, &ls);
a.push_back(fi);
ll l = fi + 1, r = fi + 1, df, op = 0;
if((ls - fi) % (N - 1) == 0){
df = (ls - fi) / (N - 1);
}else{
df = (ls - fi) / (N - 1) + 1;
}
r += df;
while(l <= ls){
ll mn, mx;
MinMax(l, r, &mn, &mx);
if(mn != -1){
a.push_back(mn);
a.push_back(mx);
}
l += df + 1;
r += df + 1;
}
ll ans = 0;
for(int i = 0;i<a.size() - 1;i++){
ans = max(ans, a[i + 1] - a[i]);
}
return ans;
}
}
