#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
const ll inf = 2e18;
const int N = 1e5 + 10;
ll n, a[N];
long long findGap(int T, int N) {
n = N;
if (T == 1) {
a[0] = -inf, a[n+1] = inf;
int l = 1, r = n;
while (l <= r) {
ll mn, mx;
MinMax(a[l-1] + 1, a[r+1] - 1, &mn, &mx);
a[l] = mn, a[r] = mx;
l++, r--;
}
ll best = 0;
for (int i = 2; i <= n; i++) {
best = max(best, a[i] - a[i-1]);
}
return best;
}
ll mn, mx;
MinMax(-inf, inf, &mn, &mx);
ll goodGab = (mx - mn - 2) / (n - 1);
ll ans = goodGab;
ll before = -1;
for (ll l = mn, r = mn + goodGab; l <= mx; l += goodGab + 1, r += goodGab + 1) {
ll minBlock, maxBlock;
MinMax(l, r, &minBlock, &maxBlock);
if (minBlock == -1) continue;
if (before != -1) ans = max(ans, minBlock - before);
before = maxBlock;
}
return ans;
}
