ref
#include "gap.h"
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll a[100005];
ll findGap(int T, int n){
if(T==1){
ll l=0, r=1000000000000000000ll, mn, mx;
int lcnt=1, rcnt=n;
while(lcnt<=rcnt && l<=r){
MinMax(l, r, &mn, &mx);
if(mn!=-1) a[lcnt++] = mn;
if(mx!=-1) a[rcnt--] = mx;
l = mn + 1;
r = mx - 1;
}
ll re=0;
for(int i=2; i<=n; i++)
re = max(re, a[i]-a[i-1]);
return re;
}
else{
ll mn, mx;
MinMax(0, 1000000000000000000ll, &mn, &mx);
if(n<=2) return mx-mn;
ll lst=mn, len=(mx-mn-1)/(n-2)+1, s=mn+1, t, ans=0, lim=mx;
for(int i=1; i<=n-2; i++){
t = s + len - 1;
if(t>=lim) t = lim - 1;
if(s>t) break;
MinMax(s, t, &mn, &mx);
if(mx!=-1){
ans = max(mn - lst, ans);
lst = mx;
}
s = t + 1;
}
ans = max(ans, lim-lst);
return ans;
}
}