/*
khoi orz, go check out his algo
-normie-
Tested with library-checker.
*/
#include <gap.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define FILE_IN "birds.inp"
#define FILE_OUT "birds.out"
#define prev prv
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define nfio cin.tie(0);cout.tie(0)
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
#define ord(a,b,c) ((a>=b)and(b>=c))
#define MOD (ll(1000000007))
#define MAX 300001
#define mag 320
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pow2(x) (ll(1)<<x)
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define For(i,__,___) for(int i=__;i<=___;i++)
#define Rep(i,__,___) for(int i=__;i>=___;i--)
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define endl "\n"
#define bi BigInt
typedef long long ll;
#define pi 3.1415926535897
//------START-----------//
ll n,m,i,j,k,u,v,t,t1,a,b,l,r,ress=0;
set<ll> se;
vector<ll> lis;
//------END-----------//
ll findGap (int T, int N)
{
n=N,t=T;
if (t==2)
{
MinMax(0,1e18,&l,&r);
lis.push_back(l);
lis.push_back(r);
u=l;
for (i=0;i<n-1;i++)
{
if (i<(r-l+1)%(n-1)) v=u+((r-l+1)/(n-1)+1); else v=u+((r-l+1)/(n-1));
MinMax(u+1,v,&a,&b);
if (a!=-1) {
lis.push_back(a);
lis.push_back(b);
}
u=v;
}
sort(lis.begin(),lis.end());
ress=0;
for (i=0;i<lis.size()-1;i++) ress=max(ress,lis[i+1]-lis[i]);
return ress;
}
else
{
l=0,r=1e18;
for (i=0;i<(n+1)/2;i++)
{
MinMax(l,r,&a,&b);
lis.push_back(a);
lis.push_back(b);
l=a+1;
r=b-1;
}
sort(lis.begin(),lis.end());
ress=0;
for (i=0;i<lis.size()-1;i++) ress=max(ress,lis[i+1]-lis[i]);
return ress;
}
}
