#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 - 1) / (n - 1);
ll ans = goodGab;
pll beforeBlock = {-1, -1};
for (ll l = mn, r = mn + goodGab; r <= mx; l += goodGab + 1, r += goodGab + 1) {
pll nowBlock;
MinMax(l, r, &nowBlock.first, &nowBlock.second);
if (nowBlock.first == -1) continue;
if (beforeBlock.first != -1) ans = max(ans, nowBlock.first - beforeBlock.second);
beforeBlock = nowBlock;
}
return ans;
}
