#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long findGap(int T, int N)
{
long long ans = 1;
if (T == 1){
long long s = -1,t = 1e18 + 1;
long long x = 0,y = 0;
vector<long long>pos(N);
int l = 0,r = N - 1;
while(l <= r && s<=t){
MinMax(s,t,&x,&y);
if (x == -1 && y == -1){
break;
}
pos[l] = x;
pos[r] = y;
--r;
++l;
s = x + 1;
t = y - 1;
}
sort(pos.begin(),pos.end());
for (int i = 1;i<N;++i){
ans = max(ans,pos[i] - pos[i - 1]);
}
}
else{
long long x,y,xx,yy;
long long s = 0,t = 1e18,lst = 0;
MinMax(s,t,&xx,&yy);
lst = xx;
long long block = (yy - xx - 2 + N) / (N - 1);
for (int i = xx;i<=yy;i+=block){
MinMax(i,i + block - 1,&x,&y);
if (x == -1)continue;
ans = max(ans,x - lst);
lst = y;
}
}
return ans;
}
