#include "bits/stdc++.h"
#include "gap.h"
#define ll long long
using namespace std;
const int N = 2e5+5;
ll a[N];
int in = 0;
ll findGap(int t, int n){
if (t == 1){
ll l = 0,r = 1e18;
ll mn,mx;
for (int i = 0;i < (n+1)>>1;i++){
MinMax(l,r,&mn,&mx);
l = mn+1;
r = mx-1;
a[in] = mn;
in++;
a[in] = mx;
in++;
}
sort(a,a+n);
ll p = 0;
for (int i = 1;i < in;i++){
p = max(p,a[i]-a[i-1]);
}
return p;
}
else {
ll mn,mx;
MinMax(1,1e18,&mn,&mx);
ll h = (mx-mn+n-2)/(n-1);
ll p = mn,x,y,l = mn,i;
for (i = mn;i+h < mx;i+=h+1){
MinMax(i,i+h,&x,&y);
if (~x){
p = max(p,x-l);
l = y;
}
}
MinMax(i,mx,&x,&y);
if (~x)
p = max(p,x-l);
return p;
}
}
