#include "gap.h"
#include<algorithm>
using namespace std;
#define MAXN 100005
const long long INF=1e18;
long long findGap(int T, int N)
{
long long s, e;
long long b[MAXN];
long long mn[MAXN], mx[MAXN];
long long a[MAXN], an;
long long ans=0;
MinMax(0, INF, &s, &e);
b[0]=s;
for(int i=1; i<N; i++){
if(i<=(e-s)%(N-1)) b[i]=b[i-1]+(e-s)/(N-1)+1;
else b[i]=b[i-1]+(e-s)/(N-1);
}
for(int i=0; i<N-1; i++) MinMax(b[i], b[i+1], mn+i, mx+i);
a[0]=-1;
a[1]=s;
a[2]=e;
an=3;
for(int i=0; i<N-1; i++) if(mn[i]!=-1){
a[an++]=mn[i];
a[an++]=mx[i];
}
sort(a, a+an);
unique(a, a+an);
for(int i=1; i<an-1; i++) if(a[i+1]-a[i]>ans) ans=a[i+1]-a[i];
return ans;
}
