#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else
#include"gap.h"
#define dbg(...) 199958
#endif
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
double pass_time=0;
/*long long findGap(int T, int N);
namespace judge{
int n;
vc<ll>a;
int cnt=0;
void MinMax(ll s,ll t,ll*mn,ll*mx){
assert(s<=t);
auto itr=lower_bound(all(a),s)-a.begin();
auto it2=upper_bound(all(a),t)-a.begin();
cnt+=it2-itr;
if(itr<n&&a[itr]<=t)*mn=a[itr];
else *mn=-1;
if(it2>0&&a[it2-1]>=s)*mx=a[it2-1];
else *mx=-1;
}
void checker(int N,vc<ll>A){
n=N,a=A;
cnt=0;
ll D=0;
rep(i,n-1)chmax(D,a[i+1]-a[i]);
if(D!=findGap(2,n)){
dbg(D);
dbg(n,A);
dbg(findGap(2,n));
assert(0);
}
assert(cnt<=3*n);
dbg("OKOK"s);
}
mt19937 mt;
void stress(){
while(1){
int n=mt()%(int)10+1;
vc<ll>a(n);
rep(i,n)a[i]=mt();
sort(all(a));
a.erase(unique(all(a)),a.end());
n=a.size();
checker(n,a);
}
}
void run(){
cin>>n;
a.resize(n);
rep(i,n)cin>>a[i];
checker(n,a);
}
};
using namespace judge;*/
long long findGap(int T, int N){
int n=N;
vc<ll>l(n+1),r(n+1);
ll*a=new ll();
ll*b=new ll();
MinMax(0,2e18,a,b);
l[0]=*a,r[0]=*b;
delete a;
delete b;
ll W=r[0]-l[0];
ll per=(W+n-1)/n;
for(int i=0;i<n;i++){
ll*a=new ll();
ll*b=new ll();
MinMax(per*i+l[0],per*(i+1)+l[0]-1,a,b);
l[i+1]=*a,r[i+1]=*b;
delete a;
delete b;
}
vc<ll>vs;
rep(i,n){
if(l[i+1]!=-1)vs.push_back(l[i+1]);
if(r[i+1]!=-1)vs.push_back(r[i+1]);
}
vs.push_back(l[0]);
vs.push_back(r[0]);
sort(all(vs));
ll ans=0;
rep(i,vs.size()-1){
chmax(ans,vs[i+1]-vs[i]);
}
return ans;
}
//int main(){judge::stress();}
