#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
const long long K=1000000000000000000LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,lef,rig,mid,f[100009],x,pas;
int B,C,D,E;
long long findGap(int T, int NN)
{
a=NN;
if(T==1){
lef=0;rig=K;
zx=0;
while(1){
if(zx*2>=a) break;
MinMax(lef,rig,&c,&d);
if(c==-1){
break;
}
if(c==d){
zx++;
f[zx]=c;
break;
}
zx++;
f[zx]=c;f[a-zx+1]=d;
lef=c+1;rig=d-1;
}
e=0;
for(i=1; i<a; i++){
e=max(e,f[i+1]-f[i]);
}
return e;
}else{
MinMax(0,K,&f[1],&f[a]);
if(a==2){
return f[a]-f[1];
}
x=(f[a]-f[1])/(a-1);
if((f[a]-f[1])%(a-1)!=0) x++;
lef=f[1]+1;
zx=f[1];
pas=0;
while(1){
if(lef>=f[a]) break;
rig=min(f[a]-1,lef+x-1);
MinMax(lef,rig,&c,&d);
if(c!=-1){
pas=max(pas,c-zx);
zx=d;
}
lef=rig+1;
}
pas=max(pas,f[a]-zx);
return pas;
}
return 0;
}
