#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long a[100005];
long long findGap(int T, int N)
{
if(T == 1){
a[0] = 0;
int r = N;
a[N + 1] = 1000000000000000006;
for(int l = 1; l <= r; l++){
MinMax(a[l - 1] + 1, a[r + 1] - 1, &a[l], &a[r]);
r--;
}
long long res = 0;
for(int l = 1; l < N; l++){
res = max(res, a[l + 1] - a[l]);
}
return res;
} else {
long long s, t;
MinMax(1, 1000000000000000000, &s, &t);
long long l, r;
l = s + 1;
long long sz = (t - s + 1) / N;
long long lf = s, res = 0;
long long a, b;
while(l < t){
r = l + sz;
MinMax(l, r, &a, &b);
if(a != -1) res = max(res, a - lf);
if(b != -1) lf = b;
l = r + 1;
}
res = max(res, t - lf);
return res;
}
}
