#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
void MinMax(long long, long long, long long*, long long*);
*/
long long findGap(int T, int N) {
// if (T == 1) {
// ll ans = 0;
// vector<ll> ini, end;
// ll l=0, r=1e18, R=0, L=0;
// while (true) {
// if (l > r) break;
// MinMax(l, r, &L, &R);
// l = L; r = R;
// if (l == -1) break;
// // cout << l << ' ' << r << '\n';
// ini.push_back(l); end.push_back(r);
// l++; r--;
// }
// reverse(end.begin(), end.end());
// ll last = ini[0];
// for (ll p : ini) {
// ans = max(ans, p-last);
// // cout << p << ' ';
// last = p;
// }
// for (ll p : end) {
// ans = max(ans, p-last);
// last = p;
// // cout << p << ' ';
// }
// // cout << '\n';
// return ans;
// }
ll L=0, R=0;
MinMax(0LL, (ll)1e18, &L, &R);
ll sz = (R-L+N-2) / (N - 1);
ll l = L, r = L + sz;
ll ans = sz;
ll last = L;
for (int i=0; i<N-1; i++, l = l+sz+1, r = min(R, r + sz+1)) {
// cout << l << ' ' << r << '\n';
ll a=0, b=0;
MinMax(l, r, &a, &b);
if (a == -1) continue;
ans = max(ans, a - last);
last = b;
if (r == R) break;
}
return ans;
}
