#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 a[MAXN];
long long b[MAXN];
long long ans=0;
long an;
a[0]=-1;
MinMax(0, INF, a+1, a+2);
b[0]=a[1]-1;
for(int i=1; i<N; i++){
if(i<=(a[2]-a[1]+1)%(N-1)) b[i]=b[i-1]+(a[2]-a[1])/(N-1)+1;
else b[i]=b[i-1]+(a[2]-a[1]+1)/(N-1);
}
for(int i=0; i<N-1; i++) MinMax(b[i]+1, b[i+1], a+i*2+3, a+i*2+4);
sort(a, a+2*N+1);
an=unique(a, a+2*N+1)-a;
for(int i=1; i<an-1; i++) if(a[i+1]-a[i]>ans) ans=a[i+1]-a[i];
return ans;
}
