#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long findGap(int t, int n) {
long long lo, hi, res;
MinMax(0, 1000000000000000000ll, &lo, &hi);
if (t == 1) {
res = 0;
for (int i = 0; i < (n + 1) / 2; i++) {
long long mn, mx;
MinMax(lo + 1, hi - 1, &mn, &mx);
if (mn == -1) break;
res = max(res, mn - lo);
res = max(res, hi - mx);
lo = mn; hi = mx;
}
res = max(res, hi - lo);
return res;
}
else {
res = (hi - lo - 1) / (n - 1) + 1;
int cnt = n - 1; long long pre = lo;
while (lo < hi) {
long long mn, mx;
MinMax(lo, lo + (hi - lo) / cnt - 1, &mn, &mx);
lo += (hi - lo) / cnt; cnt--;
if (mn == -1) continue;
res = max(res, mn - pre); pre = mx;
}
return res;
}
}
