#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+5;
const ll INF = 1000000000000000001;
ll arr[MAXN];
ll findGap(int T, int N){
if(T == 1){
arr[0] = -1; arr[N+1] = INF;
for(int i = 1;i<=(N+1)/2;++i){
ll mn,mx; MinMax(arr[i-1]+1,arr[N-i+2]-1,&mn,&mx);
arr[i] = mn; arr[N-i+1] = mx;
}
ll ans = 0;
for(int i = 1;i<N;++i){
ans = max(ans,arr[i+1]-arr[i]);
}
return ans;
}
else{
ll mn,mx;
MinMax(0,INF,&mn,&mx);
ll b = (mx-mn)/(N-1);
if((mx-mn)%(N-1) != 0) ++b;
ll ans = 0;
ll last = mn;
for(ll cur = mn;cur < mx;cur += b){
ll x = min(cur+b-1,mx-1);
ll curmn, curmx; MinMax(cur,x,&curmn,&curmx);
ans = max(ans,curmn-last);
if(curmx > 0) last = curmx;
}
ans = max(ans,mx-last);
return ans;
}
}
