#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long findGap(int T, int N)
{
int n = N;
if(T==1) {
ll l=0,r=n-1,s=0,e=1e18;
vector<ll> a(n);
ll r1=0,r2=0;
while(l<=r) {
MinMax(s,e,&r1,&r2);
a[l]=r1,a[r]=r2;
l++; r--;
s=r1+1;
e=r2-1;
}
ll res=0;
for(int i=0;i<n-1;i++) {
res=max(res,a[i+1]-a[i]);
}
return res;
}
else {
ll l,r;
MinMax(0,1e18,&l,&r);
if(n==2) return r-l+1;
ll block_size = (r-l+1) / (n-1);
ll prev=l;
ll ans=0;
for(ll i=l;i<=r;i+=block_size) {
ll mn=0,mx=0;
MinMax(i,i+block_size-1,&mn,&mx);
if(mn==-1) continue;
ans=max(ans,mn-prev);
prev=mx;
}
ans=max(ans,r-prev);
return ans;
}
}
