#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
long long ans,mn,mx;
void solve(long long l,long long r)
{
long long mn1,mx1;
long long m=(l+r)/2;
MinMax(l,m,&mn1,&mx1);
long long mn2,mx2;
MinMax(m+1,r,&mn2,&mx2);
if(mn1!=-1&&mn2!=-1)ans=max(ans,mn2-mx1);
if(mx1-mn1>mx2-mx2)
{
if(mn1!=-1&&mx1-mn1>=ans)solve(mn1,mx1);
if(mn2!=-1&&mx2-mn2>=ans)solve(mn2,mx2);
}
else
{
if(mn2!=-1&&mx2-mn2>=ans)solve(mn2,mx2);
if(mn1!=-1&&mx1-mn1>=ans)solve(mn1,mx1);
}
}
long long findGap(int t,int n)
{
solve(0,1e18);
return ans;
}
