#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long findGap(int T, int N)
{
if(T==1){
int n=N;
vector<ll> v(n);
MinMax(0ll, (ll)1e18, &v[0], &v[n-1]);
for(int i=1;i<=(n-1)/2;i++){
MinMax(v[i-1]+1, v[n-i]-1, &v[i], &v[n-i-1]);
}
ll ans=0;
for(int i=0;i<n-1;i++){
ans=max(ans, v[i+1]-v[i]);
}
return ans;
}
else if(T==2){
ll a1, an;
MinMax(0ll, (long long)1e18, &a1, &an);
ll lb=(an-a1)/(N-1) + ((an-a1)%(N-1)==0?0:1);
ll ans=lb;
vector<pair<ll,ll>> v;
for(ll l=a1;l<an;l+=lb){
ll a, b;
MinMax(l, l+lb-1, &a, &b);
//~ printf("q %lld %lld: ret %lld %lld\n", l, l+lb-1, a, b);
if(a!=-1)v.push_back({a, b});
}
v.push_back({an, an});
for(int i=0;i<(int)v.size();i++){
ans=max(ans, v[i].second-v[i].first);
if(i < (int)v.size()-1)ans=max(ans, v[i+1].first-v[i].second);
}
return ans;
}
}
