#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
struct nod
{
long long val,Min,Max;
};
nod divide(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 = divide(x,mij);
nod r = divide(mij+1,y);
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;
}
return nod{rez,Min,Max};
}
long long findGap(int t, int n)
{
return divide(1,1e18).val;
}
