//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
#define sz(x) (ll)(x.size())
#define pii pair < int, int >
#define pll pair < ll, ll >
#define debug(x) cerr << (#x) << " = " << (x) << endl
const int mod = 1e9 + 7;
const int N = 1001;
const ll OO = 1e18;
template<typename T>
bool umn (T &fi, T se) { return fi > se ? (fi = se, 1) : 0; }
template<typename T>
bool umx (T &fi, T se) { return fi < se ? (fi = se, 1) : 0; }
//vector < int > res = {1, 2, 12};
//void MinMax (ll s, ll t, ll *mn, ll *mx) {
// *mn = *mx = -1;
// for (int i = 0; i < sz(res); ++i) {
// if (res[i] >= s && res[i] <= t) {
// if (*mn == -1) *mn = res[i];
// *mx = res[i];
// }
// }
//}
ll findGap (int t, int n) {
ll a, b, mn, mx;
MinMax(0, OO, &mn, &mx);
if (t == 1) {
ll c = mn, t = mx, s = 0;
vector < ll > v;
while (c <= t) {
v.pb(c);
v.pb(t);
if (c + 1 < t)
MinMax(c + 1, t - 1, &mn, &mx);
else
break;
c = mn, t = mx;
}
sort(all(v));
for (int i = 1; i < sz(v); ++i)
s = max(s, v[i] - v[i - 1]);
return s;
}
ll s = (mx - mn + 1) / n;
ll c = mn, e = mx;
while (c < e) {
while (1) {
MinMax(c + 1, c + s, &mn, &mx);
if (mn == -1) {
MinMax(c + 1, c + s + s, &mn, &mx);
if (mn == -1)
s += s;
else {
umx(s, mn - c);
c = mx;
break;
}
} else {
umx(s, mn - c);
c = mx;
break;
}
}
}
return s;
}
//void slv () {
// cout << findGap(1, sz(res));
//}
//
//signed main () {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// int test = 1;
//// cin >> test;
// while (test--) {
// slv();
// cout << "\n";
// }
//}
