#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
long long n;
long long bck = 1000;
int pmax = 0;
struct nod
{
long long val,Min,Max;
};
long long solve1()
{
int l = 1;
int r = n;
long long st = 0, dr = 1e18;
vector<long long> a,b;
while(l<=r)
{
long long x,y;
MinMax(st,dr,&x,&y);
a.push_back(x);
b.push_back(y);
++l;
--r;
st = x + 1;
dr = y - 1;
}
vector<long long> v;
for(auto it : a)
{
v.push_back(it);
}
reverse(b.begin(),b.end());
for(auto it : b)
{
v.push_back(it);
}
long long Max = 0;
for(int i=1;i<v.size();i++)
{
Max = max(Max,v[i] - v[i-1]);
}
return Max;
}
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};
}
if(st==1 && dr==1e18)
{
pmax = (y - x + n) / (n - 1);
}
st = x, dr = y;
if(dr - st + 1 < pmax)
{
return nod{-1,x,y};
}
long long last = st - 1;
long long rez = -1;
long long Max = -1;
for(int i=1;i<=bck;i++)
{
long long mij = st + ((dr - st) / bck) * i;
if(i==bck)
{
mij = dr;
}
if(Max!=-1)
{
last = Max;
}
nod son = divide2(last+1,mij);
last = mij;
rez = max(rez,son.val);
if(Max!=-1 && son.Min!=-1)
{
rez = max(rez,son.Min - Max);
}
if(son.Max!=-1)
{
Max = son.Max;
}
if(mij==dr)
{
break;
}
}
return nod{rez,x,y};
}
long long findGap(int t, int N)
{
n = N;
if(t==1)
{
return solve1();
}
bck = min(bck,n/2);
return divide2(1,1e18).val;
}
