#include "gap.h"
#include<stack>
#include<stdio.h>
#define f MinMax
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
long long findGap(int T, int N)
{
long long s,e,ps,pe,maxx=0,x,y;
if(T==1){
f(0,(1LL<<62),&ps,&pe);
N-=2;
while(N>=2){
f(ps+1,pe-1,&s,&e);
N-=2;
maxx=max(maxx,max(s-ps,pe-e));
ps=s;pe=e;
}
if(N==1){
f(ps+1,pe-1,&s,&e);
return max(maxx,max(s-ps,pe-e));
}
return max(maxx,pe-ps);
}
f(0,(1LL<<62),&ps,&pe);
x=(pe-ps)/N;
if((pe-ps)%N) x++;
y=ps;
while(ps!=pe){
y=max(y,ps);
while(1){
f(y+1,y+x,&s,&e);
y+=x;
if(s!=-1) break;
}
maxx=max(maxx,s-ps);
x=max(x,maxx);
ps=e;
}
return maxx;
}
