#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define MOO(i, a, b) for(int i=a; i<b; i++)
#define M00(i, a) for(int i=0; i<a; i++)
#define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--)
#define M00d(i,a) for(int i = (a)-1; i>=0; i--)
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " _ " <<
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
/*vector<ll> vals;
ll m1 = 0;
ll m2 = 0;
void MinMax(ll s, ll t, ll& mn, ll& mx) {
m1++;
mn = (1e18)+1; mx = -1;
for(ll x: vals) {
if(s <= x && x <= t) {
mn = min(mn, x);
mx = max(mx, x);
m2++;
}
}
if(mx == -1) {
mn = -1;
}
}*/
pair<ll,ll> getMinMax(ll s, ll t) {
ll mn, mx;
MinMax(s, t, &mn, &mx);
return mp(mn, mx);
}
ll findGap(int t, int n) {
if(t == 1) {
vector<ll> nums;
ll lo = 0;
ll hi = 1e18;
int cnt = 0;
while(cnt < n) {
pair<ll,ll> p = getMinMax(lo, hi);
if(p.f == p.s) cnt++;
else cnt += 2;
nums.pb(p.f);
if(p.f != p.s) nums.pb(p.s);
lo = p.f+1;
hi = p.s-1;
}
sort(all(nums));
ll res = 0;
M00(i, n-1) {
res = max(res, nums[i+1] - nums[i]);
}
return res;
} else {
pair<ll,ll> p = getMinMax(0, 1e18);
ll small = p.f;
ll big = p.s;
ll cnt = big-small;
if(cnt < n) return 1;
ll blockcnt = n;
ll a = cnt/n;
ll b = a+1;
ll bcnt = cnt - a*n;
ll acnt = blockcnt - bcnt;
vector<pair<ll,ll>> blocks(blockcnt);
ll cur = small+1;
int numAs = 0;
M00(i, blockcnt) {
if(numAs < acnt) {
blocks[i] = mp(cur, cur+a-1);
cur += a;
numAs++;
} else {
blocks[i] = mp(cur, cur+b-1);
cur += b;
}
}
vector<pair<ll,ll>> answers(blockcnt);
M00(i, blockcnt) answers[i] = getMinMax(blocks[i].f, blocks[i].s);
ll res = 0;
ll last = small;
M00(i, blockcnt) {
if(answers[i].f != -1) {
res = max(res, answers[i].f - last);
last = answers[i].s;
}
}
return res;
}
}
/*bool test(vector<ll> v) {
vals = v;
ll ans = 0;
M00(i, sz(v)-1) {
ans = max(ans, v[i+1]-v[i]);
}
m1 = 0;
ll ans1 = findGap(1, sz(v));
if(2*m1 > sz(v)+1 || ans1 != ans) return 0;
m2 = 0;
ll ans2 = findGap(2, sz(v));
if(m2 > 3*sz(v) || ans2 != ans) return 0;
return 1;
}
int main() { FAST
vector<ll> v; v.pb(6); v.pb(7); v.pb(9);
cout << test(v) << "\n";
M00(i, 100) {
int n = (rand()%10)+2;
set<ll> s;
M00(j, n) s.insert(rand()%10);
vector<ll> v;
for(ll x: s) v.pb(x);
for(int x: v) cout << x << " ";
cout << "\n";
if(test(v)) cout << "OK\n";
else cout << "NO\n";
}
}
*/
