#include "gap.h"
#define ll long long
#include<iostream>
using namespace std;
template<class T>
inline bool chmax(T &a,T b){
if(a<b){a=b;return true;}
return false;
}
ll solve1(int N){
ll ans=0;
ll l=-1,r=1e18;r+=1;
for(int i=0;i<(N+1)/2;i++){
ll mn,mx;
MinMax(l+1,r-1,&mn,&mx);
if(i){
chmax(ans,mn-l);
chmax(ans,r-mx);
}
l=mn;
r=mx;
}
if(N%2==0)chmax(ans,r-l);
return ans;
}
ll solve2(int N){
ll mn,mx;
MinMax(0,1e18,&mn,&mx);
ll sz=(mx-mn+N-1)/N;
ll l=mn+1,r=mn+sz,now=mn;
ll ans=0;
for(int i=0;i<N;i++){
MinMax(l,r,&mn,&mx);
if(mn!=-1){
chmax(ans,mn-now);
now=mx;
}
l+=sz;r+=sz;
}
return ans;
}
ll findGap(int T, int N){
if(T==1)return solve1(N);
return solve2(N);
}
