#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
const ll inf = 2e18;
ll a[maxn];
ll findGap(int T, int N) {
if(T==1) {
ll L = -inf, R = inf;
for(int i=1,j=N;i<=j;i++,j--) {
MinMax(L+1,R-1,&L,&R);
a[i] = L; a[j] = R;
}
ll ans = 0;
for(int i=1;i<N;i++) ans = max(ans, a[i+1]-a[i]);
return ans;
}
else {
ll L, R;
MinMax(-inf,inf,&L,&R);
ll sz = (ll)ceil((double)(R-L-1)/(N-1));
ll ans = 0, last = L;
for(ll x=L+1;x<=R-1;x+=sz) {
ll t1, t2;
MinMax(x,min(R-1,x+sz-1),&t1,&t2);
if(t1==-1) continue;
ans = max(ans, t1-last);
last = t2;
}
ans = max(ans, R-last);
return ans;
}
}
