#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
long long findGap(int t,int n){ // Subtask 2
long long ans;
if(t==1){
long long a[n],l=0,r=1e18;
for(int i=0;i<(n+1)/2;++i){
MinMax(l,r,&a[i],&a[n-i-1]);
l=a[i]+1,r=a[n-i-1]-1;
}
ans=0;
for(int i=0;i<n-1;++i) ans=max(ans,a[i+1]-a[i]);
}else{
long long s,e;
MinMax(0,(long long)1e18,&s,&e);
vector<long long> v;
v.emplace_back(s);
ans=(long long)(e-s+n-2)/(n-1);
for(long long l=s+1;l<e;l+=ans+1){
long long a,b; MinMax(l,l+ans,&a,&b);
if(a==-1) continue;
v.emplace_back(a);
if(a!=b) v.emplace_back(b);
}
v.emplace_back(e);
for(int i=1;i<(int)v.size();++i) ans=max(ans,v[i]-v[i-1]);
}
return ans;
}
