#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
long long findGap(int _, int n) {
if (_ == 1) {
long long mn = 0, mx = 1e18;
vector<long long> a(n);
for (int l = 0, r = n - 1; l <= r; l++, r--) {
MinMax(mn, mx, &mn, &mx);
a[l] = mn;
a[r] = mx;
mn++;
mx--;
}
long long ans = 0;
for (int i = 1; i < n; i++) {
ans = max(ans, a[i] - a[i - 1]);
}
return ans;
}
long long mn = 0, mx = 1e18;
MinMax(mn, mx, &mn, &mx);
long long gap = (mx - mn + n - 2) / (n - 1);
long long l = mn, r = mx;
vector<long long> a;
while (l <= r) {
long long x = 0, y = 0;
MinMax(l, l + gap, &x, &y);
if (x != -1) {
a.push_back(x);
}
if (x != y) {
a.push_back(y);
}
l += gap + 1;
}
ranges::sort(a);
long long ans = gap;
for (int i = 1; i < a.size(); i++) {
ans = max(ans, a[i] - a[i - 1]);
}
return ans;
}
