///
/// Let the voice of love take you higher!
///
#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll ,ll > pll;
using namespace std;
#include "gap.h"
/*ll N;
vector<ll> A;
int m1, m2;
void MinMax(ll s, ll t, ll* mn, ll* mx)
{
int cnt = 0;
*mn = *mx = -1;
Loop(i,0,N)
{
if(s <= A[i] && A[i] <= t)
{
if(!cnt) *mn = A[i];
*mx = A[i];
++cnt;
}
}
m1 += 1;
m2 += cnt+1;
}*/
ll findGap(int t, int n)
{
if(t==1)
{
vector<ll> a, b;
ll l=0, r=1e18;
Loop(_,0,n/2)
{
MinMax(l,r,&l,&r);
a.push_back(l);
b.push_back(r);
++l; --r;
}
if(n&1) MinMax(l,r,&l,&r), a.push_back(l);
ll ans = 0;
Loop(i,1,a.size()) ans = max(ans, a[i]-a[i-1]);
Loop(i,1,b.size()) ans = max(ans, b[i-1]-b[i]);
ans = max(ans, b.back()-a.back());
return ans;
}
else
{
ll l=0, r=1e18;
MinMax(l,r,&l,&r);
ll tmp = (r-l+n-2)/(n-1);
ll ans = tmp;
for(ll m = l+1; m <= r; m += tmp)
{
ll mn, mx;
MinMax(m,m+tmp-1,&mn,&mx);
if(~mn){
ans = max(ans, mn-l);
l = mx;
}
}
return ans;
}
}
/*int main()
{
A = {1, 2, 3, 5, 6, (ll)1e18};
N = A.size();
cout << findGap(2, N) << '\n';
cout << m1 << ' ' << m2 << '\n';
}
*/
