#include "gap.h"
#include<vector>
// #include<iostream>
using ll=long long;
ll findGap(int t, int n)
{
if(t==2){
ll a0,an;
MinMax(0,1000000000000000000LL,&a0,&an);
int n_gap=n-1;
ll const sum_gap=an-a0;
ll const min_gap=(sum_gap+n_gap-1)/n_gap;
// std::cerr<<"a0 an min_gap="<<a0<<' '<<an<<' '<<min_gap<<'\n';
// divide [a0..an] into [a0..a0+min_gap[, [a0+min_gap..a0+2*min_gap[, ...
// the last segment should contain an
ll _,prev_end; // max value of last segment
MinMax(a0+1,a0+min_gap-1,&_,&prev_end);
if(prev_end==-1)prev_end=a0;
ll start_next=a0+min_gap;
ll ans=min_gap;
while(an>=start_next){
ll cur_start,cur_end;
MinMax(start_next,start_next+min_gap-1,&cur_start,&cur_end);
if(cur_end!=-1){
ans=std::max(ans,cur_start-prev_end);
// std::cerr<<"sg "<<start_next<<' '<<start_next+min_gap-1<<' '
// <<"ans="<<cur_start<<'-'<<prev_end<<"="<<cur_start-prev_end<<"\n";
prev_end=cur_end;
} // otherwise this segment is empty
start_next+=min_gap;
}
return ans;
}
return 0;
}
