#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
constexpr long long INF=1e18;
vector<long long> vec;
/*
void MinMax(long long s, long long t, long long &mn, long long &mx){
auto it=lower_bound(vec.begin(), vec.end(), s);
if ((it==vec.end())||(*it>t)){
mn=mx=-1; return;
}
auto it2=upper_bound(vec.begin(), vec.end(), t);
if (it2!=vec.begin())
it2--;
mn=*it, mx=*it2;
return;
}
*/
void podzad1(int N, long long &wyn){
long long t[N+1], mn=INF, mx=0;
MinMax(0, INF, &mn, &mx);
t[1]=mn, t[N]=mx;
for (int i=2; i<=(N+1)/2; i++){
mn=INF, mx=0;
MinMax(t[i-1]+1, t[N-(i-2)]-1, &mn, &mx);
t[i]=mn, t[N-(i-1)]=mx;
}
for (int i=1; i<N; i++){
wyn=max(wyn, t[i+1]-t[i]);
}
return;
}
void podzad2(int N, long long &wyn){
long long n=N;
vector<long long> war;
long long pier=INF, ost=0, prz, pom;
MinMax(0, INF, &pier, &ost);
war.push_back(pier);
if (n<=2){
wyn=ost-pier;
return;
}
prz=(ost-pier)/(n-1);
for (long long i=pier+1LL; i+prz<=ost; i+=prz+1LL){
long long a=INF, b=0;
MinMax(i, i+prz, &a, &b);
pom=i+prz+1;
if ((a!=(long long)(-1))&&(a!=b))
war.push_back(a), war.push_back(b);
else if (a!=(long long)(-1))
war.push_back((a));
}
long long a=INF;
MinMax(pom, max(pom, ost), &a, &ost);
war.push_back(a);
war.push_back(ost);
for (int i=1; i<war.size(); i++){
wyn=max(wyn, war[i]-war[i-1]);
}
return;
}
long long findGap(int T, int N){
long long wyn=0;
if (T==1)
podzad1(N, wyn);
else
podzad2(N, wyn);
return wyn;
}
/*
int main(){
int T, N; long long a, pom=0; cin >> T >> N;
for (int i=0; i<N; i++){
cin >> a, vec.push_back(a);
if (i)
pom=max(pom, vec[i]-vec[i-1]);
}
cout << findGap(T, N);
cout << pom;
}
*/
