#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll A[100005];
ll findGap(int T, int N) {
if (T == 1) {
ll a = -1, b = 1e18 + 1;
int l = 0, r = N - 1;
while(l <= r) {
MinMax(a + 1, b - 1, &a, &b);
A[l++] = a; A[r--] = b;
}
a = 0;
for (int i = 1; i < N; i++) a = max(a, A[i] - A[i - 1]);
return a;
} else {
ll a, b, res = 0;
MinMax(0, 1e18, &a, &b);
if (b - a + 1 == N) return 1;
ll sz = (b - (a + 1)) / (N - 1);
/// [a + 1, a + sz + 1], [a + sz + 2, a + ]
ll last = a, X, Y;
for (ll x = a + 1; x <= b - 1; x += sz + 1) {
/// [x, x + sz]
MinMax(x, x + sz, &X, &Y);
res = max(res, X - last);
last = Y;
}
return max(res, b - last);
}
return 0;
}
