#include "gap.h"
#include<bits/stdc++.h>
const long long INF = 1e18 + 6;
using namespace std;
long long a[100005];
long long findGap(int T, int N)
{
if(T == 1){
int l = 0;
int r = N - 1;
long long mn = 0, mx = INF;
long long h,h1;
while(l <= r){
MinMax(mn, mx, &h, &h1);
a[l] = h;
a[r] = h1;
l++;
r--;
mn = h + 1;
mx = h1 - 1;
}
long long ans = 0;
for(int i = 1; i < N; i++){
ans = max(ans,a[i] - a[i - 1]);
}
return ans;
}
else{
long long mn,mx;
MinMax(0, INF, &mn, &mx);
a[0] = mn;
a[N] = mx;
long long x = (mx - mn + N - 2) / (N - 1) + 1;
long long ans = x - 1;
long long l = mn + 1, last = mn;
while(last + x < a[N]){
MinMax(l, l + x - 1, &mn, &mx);
if(mn == -1){
l += x;
} else{
ans = max(ans, mn - last);
last = mx;
l = last + 1;
}
x = max(ans, x + 1);
}
return ans;
}
}
