#include "gap.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
ll findGap(int sub, int n)
{
ll a[nx];
if(sub==1)
{
ll l=0, r=1e18, mn, mx;
int i=1, j=n;
while(i<=j)
{
MinMax(l, r, &mn, &mx);
a[i]=mn, a[j]=mx;
i++, j--;
l=mn+1, r=mx-1;
}
ll res=0;
for(int i = 1; i < n; i++)
res=max(res, a[i+1]-a[i]);
return res;
}
ll l, r;
MinMax(0, 1e18, &l, &r);
if(r-l+1==n)
return 1;
ll lim=r, gap=ceil(1.0*(r-l)/(n-1)), cur=l, nxt=l, res=0;
while(cur<lim)
{
MinMax(cur+1, cur+gap, &l, &r);
if(l!=-1)
{
res=max(res, l-nxt);
nxt=r;
}
cur+=gap;
}
res=max(res, lim-nxt);
return res;
}
