#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
struct nod
{
long long val,Min,Max;
};
nod divide1(long long st, long long dr)
{
if(st > dr)
{
return nod{-1,-1,-1};
}
long long x,y;
MinMax(st,dr,&x,&y);
if(x==-1)
{
return nod{-1,-1,-1};
}
if(x==y)
{
return nod{-1,x,y};
}
long long mij = (x + y) >> 1;
nod l = divide1(x+1,mij);
nod r = divide1(mij+1,y-1);
long long rez = -1;
if(l.Max!=-1 && r.Min!=-1)
{
rez = max(rez,r.Min-l.Max);
}
rez = max(rez,l.val);
rez = max(rez,r.val);
long long Max = max(l.Max,r.Max);
long long Min;
if(l.Min==-1)
{
Min = r.Min;
}
else
{
Min = l.Min;
}
if(Min!=-1)
{
rez = max(rez,Min - x);
}
if(Max!=-1)
{
rez = max(rez,y - Max);
}
return nod{rez,x,y};
}
nod divide2(long long st, long long dr)
{
if(st > dr)
{
return nod{-1,-1,-1};
}
long long x,y;
MinMax(st,dr,&x,&y);
if(x==-1)
{
return nod{-1,-1,-1};
}
if(x==y)
{
return nod{-1,x,y};
}
long long mij = (st + dr) >> 1;
nod l = divide2(st,mij);
nod r = divide2(mij+1,dr);
long long rez = -1;
if(l.Max!=-1 && r.Min!=-1)
{
rez = max(rez,r.Min-l.Max);
}
rez = max(rez,l.val);
rez = max(rez,r.val);
return nod{rez,x,y};
}
long long findGap(int t, int n)
{
return divide2(1,1e18).val;
}
