#include <bits/stdc++.h>
#include "gap.h"
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
#define ll long long
const ll inf = 1e18;
ll findGap (int t, int n) {
if(t == 1) {
std::vector <ll> v(n+2);
v[0] = -1, v[n+1] = inf + 1;
for(int i=1; i<=n-i+1; ++i)
MinMax (v[i-1]+1, v[n-i+2]-1, &v[i], &v[n-i+1]);
ll ans = 0;
FOR(i,2,n) ans = std::max(ans, v[i] - v[i-1]);
return ans;
} else {
ll Mn, Mx, B, ans, lst, L, R;
MinMax (0, inf, &Mn, &Mx);
ans = B = (Mx - Mn + n - 2) / (n - 1);
lst = Mn;
for(ll i=Mn+1; i<Mx; i+=B) {
MinMax (i, i+B-1, &L, &R);
if(L == -1) continue;
ans = std::max(ans, L - lst);
lst = R;
}
return ans;
}
}
