#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
#define debug(x) cerr << #x << ": " << x << endl;
#define sep ' '
#define all(x) (x).begin(),(x).end()
const ll INF = 2e18;
ll findGap(int t, int n) {
if (t == 1) {
ll l = -1, r = INF;
vector<ll> vec;
int t = (n + 1) >> 1;
while (t-- && l < r) {
MinMax(l, r, &l, &r);
if (l != -1) {
vec.push_back(l);
vec.push_back(r);
}
l++;
r--;
}
sort(all(vec));
ll ans = 0;
for (int i = 1; i < int(vec.size()); i++)
ans = max(ans, vec[i] - vec[i - 1]);
return ans;
}
ll mn = 0, mx = INF;
MinMax(0, INF, &mn, &mx);
if (n == 1) return 0;
ll len = mx - mn;
ll sq = (len + n - 2) / (n - 1), ans = sq;
vector<ll> vec;
for (ll l = mn; l <= mx; l += sq + 1) { // sq + 1
ll a = 0, b = 0;
MinMax(l, l + sq, &a, &b); //
if (a >= 0) {
if (!vec.empty()) ans = max(ans, a - vec.back());
vec.push_back(b);
}
}
return ans;
}
