#include<bits/stdc++.h>
using namespace std;
#include "gap.h"
long long t,n,st,ed,mn,mx,ans=-1e18,gap,num;
vector<long long> l,r;
vector<pair<long long,long long> > p;
long long findGap(int T, int N)
{
t=(long long)T;
n=(long long)N;
if(t==1)
{
st=0;
ed=1e18;
for(int i=1;i<=(n-1)/2+1;i++)
{
MinMax(st,ed,&mn,&mx);
l.push_back(mn);
r.push_back(mx);
st=mn+1;
ed=mx-1;
}
for(int i=1;i<l.size();i++)
{
ans=max(ans,l[i]-l[i-1]);
}
ans=max(ans,r[r.size()-1]-l[l.size()-1]);
for(int i=r.size()-2;i>=0;i--)
{
ans=max(ans,r[i]-r[i+1]);
}
return ans;
}else
{
MinMax(1,1e18,&st,&ed);
//printf("%lld %lld\n",st,ed);
p.push_back({st,st});
gap=(ed-st)/(n-1);
ans=gap;
num=st+1;
while(1)
{
MinMax(num,num+gap,&mn,&mx);
//ans=max(ans,mn-num);
if(mn!=-1&&mx!=-1)
p.push_back({mn,mx});
num+=gap;
if(num>=ed)
{
break;
}
}
for(int i=0;i<p.size();i++)
{
//printf("%lld %lld\n",p[i].first,p[i].second);
if(i!=0)ans=max(ans,p[i].first-p[i-1].second);
ans=max(ans,p[i].second-p[i].first);
}
return ans;
}
}
