#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mxN = 4e5 + 5;
using namespace std;
long long findGap(int T, int N)
{
ll l,r;
MinMax(0,1e18,&l,&r);
if(r - l + 1 == N) return 1;
if(T == 1){
vector<ll>v;
v.push_back(l);
v.push_back(r);
l++;
r--;
N -= 2;
while(N > 0){
MinMax(l,r,&l,&r);
if(l == -1 || r == -1) break;
v.push_back(l);
v.push_back(r);
l++;
r--;
N -= 2;
}
sort(v.begin(),v.end());
ll bg = v[0];
ll ans = 0;
for(auto x : v){
ans = max(ans,x - bg);
bg = x;
}
return ans;
}
ll buck = (r - l + 1) / N;
buck += (((r - l + 1) % N) != 0);
ll prvT = -1;
ll ans = buck;
buck++;
for(ll i = l; i <= r;i += buck){
ll s = i,t = min(r, i + buck - 1);
ll mx,mn;
MinMax(s,t,&mn,&mx);
// cout<<s<<' '<<t<<' '<<mx<<' '<<mn<<'\n';
if(prvT != -1 && mn != -1) ans = max(ans, mn - prvT);
if(mx != -1) prvT = mx;
}
return ans;
}
