#include <bits/stdc++.h>
#include <gap.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
const ll Mod = 1000000007;
const int maxN = 1e5 + 1;
const ll inf = LLONG_MAX;
int n;
ll a[maxN];
ll findGap(int T, int N){
if (T & 1){
ll mn, mx;
MinMax(0, inf, &mn, &mx);
a[1] = mn, a[N] = mx;
for (int i = 2; i <= (N + 1) / 2; ++i){
MinMax(mn + 1, mx - 1, &mn, &mx);
a[i] = mn, a[N - i + 1] = mx;
}
ll ans = 0;
for (int i = 2; i <= N; ++i){
ans = max(ans, a[i] - a[i - 1]);
}
return ans;
}
else{
ll mn, mx;
MinMax(0, inf, &mn, &mx);
ll ans = 0, last = LLONG_MAX;
ll j = (mx - mn) / (N - 1);
for (ll i = mn; i < mx; i += j + 1){
ll x, y;
MinMax(i, i + j, &x, &y);
if (x == -1) continue;
ans = max(ans, x - last);
last = y;
}
if (N == 2) return mx - mn;
return ans;
}
}
